Implement a function to check if a linked list is a palindrome in c++

Question

This is working example, I'm interested in mostly in knowing if there is any c++ related improvements you guys suggest? Also, do you think its better to solve this question iteratively or interviewer would prefer some recursive solution (assuming if that is possible)? Any other suggestions from interview point of view welcome?

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>

template<typename valT>
struct node
{
  valT val;
  node<valT> *next;
  node() { next = nullptr; }
  node(valT v) : val(v),next(nullptr) { }
  ~node() { next = nullptr; }
};

using myNode = node<int>;
using myNodePtr = myNode *;
myNodePtr head = nullptr; 

void showLL(myNodePtr head)
{
 std::cout << "Linked List =>";
 while(head){
   std::cout << head->val << ", ";
   head = head->next;
 }
 std::cout << std::endl;
}

int main(int argc, char **argv)
{
  myNodePtr prev = nullptr;
  for( int i = 1; i < argc ; i++ ) {
    myNodePtr tmp = new myNode(strtol(argv[i], NULL, 10));
    if(!head) {
      head = tmp;
    }
    if(prev){
      prev->next = tmp;
    } 
    prev = tmp;
  }

  std::cout << "Input "  << std::endl;
  showLL(head);

  //Find middle
  //Push on stack until you find middle
  //Stop fast runner and pop back and compare and break if not same

  //Palindrome loop
  myNodePtr middleNode = nullptr;
  std::vector<int> stack;
  for(myNodePtr slowRunner = head, fastRunner = head; slowRunner; slowRunner = slowRunner->next) {
    if(!middleNode) {
      stack.push_back(slowRunner->val);

      if(fastRunner->next) {
        if(fastRunner->next->next) { //odd
          fastRunner = fastRunner->next->next;
          if(!fastRunner->next) {
            slowRunner = slowRunner->next;
          }
        } else { //even
          fastRunner = fastRunner->next;
        }
        if(!fastRunner->next) {
          middleNode = slowRunner;
          std::cout << "middle node =" << slowRunner->val << std::endl;
        }
      }
    } else {
      //even odd
      if( stack.back() != slowRunner->val) {
        std::cout << "Not a palindrom!" << std::endl;
        return 1; //delete all linked lists
      }
      stack.pop_back();
    }
  }

  std::cout << "is Palindrome"<< std::endl;
}

Was it your goal to write your own linked list instead of using std::list? — Zeta
– Zeta, Commented Sep 2, 2017 at 15:19

janos · Accepted Answer · 2017-09-02 15:29:00Z

Building linked list from command line arguments

The multiple conditionals inside this loop is kind of ugly, because head and prev will only ever be null once:

  for( int i = 1; i < argc ; i++ ) {
    myNodePtr tmp = new myNode(strtol(argv[i], NULL, 10));
    if(!head) {
      head = tmp;
    }
    if(prev){
      prev->next = tmp;
    } 
    prev = tmp;
  }

You could avoid the unnecessary conditional evaluations by lifting the special treatment of the head outside the loop:

  myNodePtr head = nullptr;
  if (argc > 1) {
    head = new myNode(strtol(argv[1], NULL, 10));
  }
  myNodePtr node = head;
  for (int i = 2; i < argc; i++) {
    node->next = new myNode(strtol(argv[i], NULL, 10));
    node = node->next;
  }

Iterating until the middle and verifying the rest

Iterating until the middle could be written simpler:

  std::vector<int> stack;
  myNodePtr slow = head;
  myNodePtr fast = head;
  while (fast && fast->next) {
    stack.push_back(slow->val);
    slow = slow->next;
    fast = fast->next->next;
  }

At this point, if the length is odd, slow will be pointing to the single middle element, that should be skipped. The length is odd if fast is not null, so you can write:

  if (fast) slow = slow->next;

Finally, to check that the rest of the list matches the content of the stack:

  while (!stack.empty()) {
    if (stack.back() != slow->val) {
      std::cout << "Not a palindrom!" << std::endl;
      return 1;
    }
    stack.pop_back();
    slow = slow->next;
  }

This alternative implementation uses much fewer conditions and cleanly separates the interesting steps, so I think it's easier to read.

From an interview point of view

At an interview, if you write an iterative solution, the interviewer is likely to ask to also write a recursive solution. And vice versa. You need to be able to ready to do both, and discuss about the trade-offs of each technique.

This solution would get important criticism at an interview for several reasons:

Large chunk of code inside main method, instead of separated to small methods with single simple clear purpose
Knowledge of memory management is not demonstrated (the program simply relies on cleanup on exit)

Stack Exchange Network

Implement a function to check if a linked list is a palindrome in c++

1 Answer 1

Building linked list from command line arguments

Iterating until the middle and verifying the rest

From an interview point of view

You must log in to answer this question.

Hot Network Questions

Implement a function to check if a linked list is a palindrome in c++

1 Answer 1

Building linked list from command line arguments

Iterating until the middle and verifying the rest

From an interview point of view

You must log in to answer this question.

Related

Hot Network Questions