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 <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.
Checking if a single linked list is a palindrome in C++
c++;c++11;linked list;palindrome