Palindrom Linked List | Leetcode 234.

Palindrom Linked List | Leetcode 234.

In this article, we will look at the palindrome linked list problem and solve this problem using fast and slow pointer design patterns.

Before trying to solve the problem, let's understand what the problem is. We recommend giving it a try by yourself before going through the article. Find the problem here

Problem Description :

Given the head of a singly linked list, return true if it is a palindrome.

In order to solve this problem, we will use the Fast and Slow Pointer Design pattern.

When a list is a palindrome, they read the same from forward direction as well as from the backward direction. Another property of palindrome is if we reverse them from the middle, the first half will be the same as the second half of the list.

So for our solution, we will find the middle of the LinkedList using fast and slow pointer algorithms. Basically, when the fast pointer moves double the speed of the slow pointer and reaches the end, at the point, the slow pointer will reach the middle of the list.

Once we find the middle of the list, we will reverse the list starting from the middle node.

After reversing the list from the middle, we will compare the first half of the list with the second half. If both halves are equal then we can conclude that they are palindrome.

Here is a solution to the problem.


public boolean isPalindrome(ListNode head) {
      
       
       // Step 1 : find the middle of linked list
       ListNode fastPointer = head;
       ListNode slowPointer = head;
       
       while (fastPointer != null && fastPointer.next != null  ) {
           slowPointer = slowPointer.next;
           fastPointer = fastPointer.next.next;
       }
       
       
       
       //Step 2 : reverse the from of middle linked list and compared
       ListNode currentNode = slowPointer;
       ListNode nextNode = slowPointer;
       ListNode prevNode = null;
       
       while (currentNode != null) {
           nextNode = nextNode.next;
           currentNode.next = prevNode;
           prevNode = currentNode;
           currentNode = nextNode;
       }
       
       //Step 3 : comparing first half and second half
       
       while (prevNode != null && head != null ) {
           if(head.val != prevNode.val) {
               return false;
           }
           head = head.next;
           prevNode = prevNode.next;
       }
       return true;
   }