patterncppMinor
Checking if a single linked list is a palindrome in C++
Viewed 0 times
checkingpalindromesinglelistlinked
Problem
The following is my first try at this classical interview question. It is quiet different from the solutions Gayle Laakmann provides in her book, and in another question on stackoverflow, someone initially mentioned there are better ways to do it.
-
I think my solution should run in O(n) time and use O(n) space. Would better Big O performance be possible? This question claims to do it in O(1) space, but edits the list in place, which in my opinion is not a valid solution (A function checking something should always leave the "something" unchanged).
-
Are there any other things I should change, especially concerning C++ style? I guess I could be using a stack instead of a vector to save the iterators, would that be of any advantage?
This should compile in any compiler using C++11 / C++14.
-
I think my solution should run in O(n) time and use O(n) space. Would better Big O performance be possible? This question claims to do it in O(1) space, but edits the list in place, which in my opinion is not a valid solution (A function checking something should always leave the "something" unchanged).
-
Are there any other things I should change, especially concerning C++ style? I guess I could be using a stack instead of a vector to save the iterators, would that be of any advantage?
#include
#include
#include
#include
template
bool isPalindrome(const std::forward_list& lf)
{
auto iter = lf.begin();
std::vector bv; // =istop; i--, iter++)
{ if( *iter != *(bv[i])) return false; }
return true;
}
int main(int argc, char* argv[])
{
std::forward_list list = {0,1,2,1,0};
std::cout << "Is palindrome: " << isPalindrome(list) << std::endl;
return 1;
}This should compile in any compiler using C++11 / C++14.
Solution
I see some things that may help you improve your code.
Omit unused variables
Neither
Consider the value of simplicity
While your code is correct and likely more efficient, there is often merit in creating a program that is so simple it is obviously defect-free. Such a routine could be this:
The advantage to this is that it may be sufficiently fast, depending on your needs. If it is, then you're done. If it's not, you can use the code as a benchmark to both verify both the correctness and speed of any alternate versions.
Use the data structure to your advantage
Rather than using a
Count rather than calculate
Since you're iterating through the list anyway, you could simply count the number of items as you go. The current code has this somewhat complicated calculation:
Consider instead that if your code simply increments
Omit the
Usually, a program that ends main with a non-zero return signifies an error to the operating system. This program always returns
A worked example
Here's an alternative approach incorporating the ideas above:
Omit unused variables
Neither
argc nor argv are used in this program and should be eliminated.Consider the value of simplicity
While your code is correct and likely more efficient, there is often merit in creating a program that is so simple it is obviously defect-free. Such a routine could be this:
auto bv{lf};
bv.reverse();
return bv == lf;The advantage to this is that it may be sufficiently fast, depending on your needs. If it is, then you're done. If it's not, you can use the code as a benchmark to both verify both the correctness and speed of any alternate versions.
Use the data structure to your advantage
Rather than using a
std::vector, it may be better to use std::forward_list for the copy. Doing so would allow you to do use the push_front() operator which is quite efficient. That would avoid having to have a std::vector and the possible resizing operations that can occur while adding to it.Count rather than calculate
Since you're iterating through the list anyway, you could simply count the number of items as you go. The current code has this somewhat complicated calculation:
int istop = bv.size()/2 + bv.size()%2;Consider instead that if your code simply increments
istop during the copy loop, it could simplify to this:istop /= 2;Omit the
return in mainUsually, a program that ends main with a non-zero return signifies an error to the operating system. This program always returns
1 which many operating systems will interpret as an abnormal end to the program. Simplify your code by simply omitting the return; when main ends without a return, the compiler automatically creates the code equivalent to return 0;.A worked example
Here's an alternative approach incorporating the ideas above:
template
bool isPalindrome(const std::forward_list& lf)
{
auto iter = lf.begin();
std::forward_list bv;
int sz = 0;
for ( ; iter != lf.end(); ++iter) {
bv.push_front(iter);
++sz;
}
sz /= 2;
iter = lf.begin();
for (auto it2 = bv.begin(); sz; --sz, ++iter, ++it2) {
if (**it2 != *iter) return false;
}
return true;
}Code Snippets
auto bv{lf};
bv.reverse();
return bv == lf;int istop = bv.size()/2 + bv.size()%2;istop /= 2;template<typename T>
bool isPalindrome(const std::forward_list<T>& lf)
{
auto iter = lf.begin();
std::forward_list<decltype(iter)> bv;
int sz = 0;
for ( ; iter != lf.end(); ++iter) {
bv.push_front(iter);
++sz;
}
sz /= 2;
iter = lf.begin();
for (auto it2 = bv.begin(); sz; --sz, ++iter, ++it2) {
if (**it2 != *iter) return false;
}
return true;
}Context
StackExchange Code Review Q#124470, answer score: 2
Revisions (0)
No revisions yet.