Find if a linked list is a palindrome or not

Problem:

Given the head of a linked list , find if it is a palindrome or not.

Find the solution in O(n) time and in place (O(1) space complexity)

For example , the below linked list :

1 -> 2 -> 2 -> 1 is a palindrome

The below is not:

1 -> 5 -> 4 -> 1

Try out the solution here:

https://leetcode.com/problems/palindrome-linked-list/

Solution:

If we don’t have to solve this problem in O(1) time complexity , the solution is relatively easier.

Go through each node from the start and collect the values in an array.

Then maintain two pointers to the array one at the starting and one at the ending.

Increment the start pointer and decrement the end pointer at the same time and compare the values until both pointers don’t collide

If they are not the same at any point return false.

To solve this in place though we can follow the below approach.

• Reverse the second half of the linked list
• Compare the two half elements one by one , if they don’t match at any point return false.

How can you reverse the second half?

For this,

You need to find which is the half element.

To do this you can use a slow pointer and a fast pointer.

Let the slow pointer move one step at a time.

And the fast pointer move two steps at a time.

By the time the fast pointer reaches the end you would have reached the half.

Here is the code:

   ListNode slow = head;
        
        
        ListNode fast = head;
        
  
        
        //find middle
        
        while(fast!= null && fast.next != null){
            
            
            slow = slow.next;
            
            fast = fast.next.next;
            
            
        }

Once we reach the middle, we need to point to the beginning of the second half.

This would automatically happen in the above code if the number of nodes is even.

But if the number of nodes is odd then we would be pointing to the middle element AND fast pointer would not be null.

So if fast pointer is not null (meaning the number of nodes is odd) move the pointer pointing to the middle element by one position so that it points to the head of the second half:

  if(fast != null) slow = slow.next;

Now we have got a pointer to the head of the second half.

What about the first half?

We have the head pointer .

But let’s not modify the head pointer.

Let’s use the fast pointer to point to head now.

  fast = head;
   

Now we have got two pointers.

The slow pointer pointing to the head of the second half.

The fast pointer pointing to the head of the first half.

Now let’s reverse the second half.

After reversing if the first and second halves match then the linked list represents a palindrome.

Below is the code to reverse the second half:

 ListNode newNode = null;
        
        
        while(slow != null){
            
        
            ListNode next = slow.next;
            
            
            slow.next = newNode;
            
            newNode = slow;
            
            slow= next;
            
            
            
        }

In the above code the pointer “newNode” now points to the head of the second half.

Now let’s move the pointers one step at a time and compare each element in each half.

At any point if they don’t match we will return false:

     
        
        while(newNode!= null && fast!=null){
            
            
            if(newNode.val != fast.val ) return false;
            
            newNode =newNode.next;
            
            fast = fast.next;
            
        }

Here is the entire code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        
        
        if(head.next == null) return true;
        
        ListNode slow = head;
        
        
        ListNode fast = head;
        
  
        
        //find middle
        
        while(fast!= null && fast.next != null){
            
            
            slow = slow.next;
            
            fast = fast.next.next;
            
            
        }
        
   
    if(fast != null) slow = slow.next;
        
        fast = head;
        
   
      ListNode newNode = null;
        
        
        while(slow != null){
            
        
            ListNode next = slow.next;
            
            
            slow.next = newNode;
            
            newNode = slow;
            
            slow= next;
            
            
            
        }
        
        

     
        
        while(newNode!= null && fast!=null){
            
            
            if(newNode.val != fast.val ) return false;
            
            newNode =newNode.next;
            
            fast = fast.next;
            
        }
        
        
        return true;
        
        
    }
}

Time complexity:

Finding the middle element takes O(n) time complexity. Slow pointer moves through n/2 elements and fast pointer moves through n elements , so total time complexity is O(n)

Reversing the second half takes O(n/2) time which is equal to O(n)

And finally comparing the two halves takes O(n/2) time which is equal to O(n)

So total time complexity is O(n)

Space complexity:

We are not using any extra space complexity so space complexity is O(1)