Linked list is a palindrome or Not

In this article, we discussed a problem: How to check given linked list is palindrome or not in O(n) time complexity means in single traverse.

Any number or word which found the same, either you read them from forwards or backwards then they are palindrome.

What is palindrome?

To determine, given linked list is palindrome or not. We are using two pointer approach, one is a slow pointer and second is the fast pointer.
Pointers are variables, variables can be called by many names like object referencer, reference holder, etc. As usual, the slow pointer jumps one step which means jumps from the current node to the next node and fast pointer jumps two-step from the current node to the next node to the next node.

Note: A current node is a node where pointers are pointing to the node either it is a slow pointer or fast pointer.

Algo which we follow here:
1. Divide the linked list into parts: In this, we divide the given linked list into two parts, given linked list can be even in size or odd in size.

If the linked list is odd in size then ignore the middle node and put NULL into the next, previous node of the middle node. By putting NULL, we create the two LinkedList and the middle node is ignored and removed. If the linked list is even in size then we divide into parts without ignoring any node by put NULL into the next of the middle node.

Explanation using slow and fast pointer variables:
When the fast pointer reaches null (in case of even size LinkedList) or fast pointer is not null but the fast pointer next having null as a value (in case of odd size LinkedList). Null is a literal and whenever we found it is the last node of the linked list or we reach Null literal.

Same time, the slow pointer is also reached on the middle node. From here, update slow pointer next with the null value and new pointer introduces by the name of second_head, it is the start of the second part of the linked list. Below is the code and sample input is:
Odd Size list: 1 => 2 => 3 => 4 => 3 => 2 => 1.
Even Size list: 1 => 2 => 3 =>4 => 4=>3=> 2 => 1 .

 while(true) {
         fast_p = fast_p-->next-->next;
         if(fast_p != NULL && fast_p-->next!=NULL) {
                 second_head = slow_p-->next-->next;
                 break;  
          }
          if(fast_p==null) {
                  second_head = slow_p-->next;
                  break;
          }
          slow_p = slow_p-->next;
 }
 slow_p-->next=NULL;

2. Reverse the LinkedList: We need to reverse the second part of the linked list, For Reverse a linked list, please refer linked post. Result:
Odd size list: 4 is ignored.
First list: 1=>2=>3
Second list: 1=>2=>3

Even size list:
First list: 1=>2=>3=>4
Second list: 1=>2=>3=>4

3. Compare the first and second part of the linked list to check and get to know that Complete LinkedList is palindrome or Not.