Checking if a single linked list is a palindrome in C++

Question

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.

1. 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).

2. 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 <forward_list>
#include <iostream>
#include <cstdlib>
#include <vector>

template<typename T>
bool isPalindrome(const std::forward_list<T>& lf)
{
  auto iter = lf.begin();
  std::vector<decltype(iter)> bv; // <-- 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>=istop; i--, iter++)
  { if( *iter != *(bv[i])) return false; }
  return true;
}

int main(int argc, char* argv[])
{
  std::forward_list<int> 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.

Answer 1

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<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;
}

Answer 2

If you're using a stack, you'd need to store N / 2 items into the stack to check if the list is a palindrome rather than store N iterators like you do now. So while O (N / 2) is still O (n) in terms of space complexity, you'd be saving half your memory usage in practice. Also, there's no real reason to store iterators in the data structure when you could just store the type (T) itself. This is not only more expressive of your intent (that you'll be comparing an object of type T to another object of type T, but it makes the code a little easier to write and read :)

Also, since you're using C++11 / C++14, get used to using auto. It'll automatically get the correct type for you (most of the time) and you won't have to worry about writing out long type names (e.g. std::forward_list<T>::size_type).

Here is the code:

#include <forward_list>
#include <iostream>
#include <iterator>
#include <cstdlib>
#include <stack>

template <class T>
bool isEven(T num)
{
    return num != 0 && (num & 1) == 0;
}

template<typename T>
bool isPalindrome(const std::forward_list<T>& lf)
{
  if (lf.empty()) {
      return true; // or false? Depends on how you see it.
  }

  const auto size = std::distance(lf.begin(), lf.end()); // forward_list's size is O (n)
  auto midItr = lf.begin();
  std::advance(midItr, isEven(size) ? size / 2 : (size / 2) + 1);

  std::stack<T> st;
  for (auto i = lf.begin(); i != midItr; ++i) {
      st.push(*i);
  }

  // in lists with odd # of elements, we want to make sure we advance midItr.
  // Example: 1 -> 2 -> 1
  //               ^-- this is midItr. If we keep it here, below checks fail.
  if (!isEven(size)) {
      ++midItr;
  }

  for (; !st.empty() && midItr != lf.end(); ++midItr) {
      if (*midItr != st.top()) {
          return false;
      }
      st.pop();
  }
  return st.empty();
}

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