Checking if a single linked list is a palindrome in C++ 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?




#include &lt;forward_list&gt;
#include &lt;iostream&gt;
#include &lt;cstdlib&gt;
#include &lt;vector&gt;

template&lt;typename T&gt;
bool isPalindrome(const std::forward_list&lt;T&gt;&amp; lf)
{
  auto iter = lf.begin();
  std::vector&lt;decltype(iter)&gt; bv; // &lt;-- Correct usage?

  while(iter!= lf.end())
    { bv.push_back(iter++); }

  int istop = bv.size()/2 + bv.size()%2;
  iter = lf.begin();

  for(int i = bv.size()-1; i&gt;=istop; i--, iter++)
  { if( *iter != *(bv[i])) return false; }
  return true;
}

int main(int argc, char* argv[])
{
  std::forward_list&lt;int&gt; list = {0,1,2,1,0};
  std::cout &lt;&lt; "Is palindrome: " &lt;&lt; isPalindrome(list) &lt;&lt; std::endl;
  return 1;
}


This should compile in any compiler using C++11 / C++14.
I see some things that may help you improve your code.

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 main

Usually, 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&lt;typename T&gt;
bool isPalindrome(const std::forward_list&lt;T&gt;&amp; lf)
{
    auto iter = lf.begin();
    std::forward_list&lt;decltype(iter)&gt; 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;
}