This is our given problem,

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

How can we APPROACH this problem?

By using two ways, we can solve this problem,

  1. Slow and Fast Pointer Approach
  2. Reversing the Linked List

If you do not know, how to reverse the linked list, I already made an article with clear explanation of how to reverse the linked list with both iterative and recursive approach.

Slow and Fast Pointer Approach

  1. Slow pointer moves by one position
  2. Fast pointer moves by two positions
Consider the below example, 

head = 1->2-1->2->1->null

slow = head;
//slow = 1->2-1->2->1->null

slow = head;
//slow = 1->2-1->2->1->null

fast = head;
//fast = 1->2-1->2->1->null
//iteration first time
while(fast != null && fast.next != null)
{
slow = slow.next;
//slow = 2-1->2->1->null
fast = fast.next.next;
//fast = 1->2->1->null
}
//iteration second time
while(fast != null && fast.next != null)
{
slow = slow.next;
//slow = 1->2->1->null
fast = fast.next.next;
//fast = 1->null
}
Since fast.next == null, it comes out of the while loop

Still now we have,
slow = 1->2->1->null;
fast = 1->null;

We have odd length of linked list, so that we have to ignore the middle node,
in this case, for slow = 1->2->1->null, ignore the 1st node,

How can we ignore that, move the slow pointer to the next position.

Note:
if fast == null, it means we have even length linked list
if fast != null, it means we have odd length linked list

if(fast != null)
{
slow = slow.next;
//slow = 2->1->null
}

Now reverse the slow linked list, then it becomes
slow => 1-2->null;

Assign head pointer to fast;
head = 1->2->null;
fast = 1->2->null;

Iterate one by one,
Compare each other, if it is not equal return false.

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        //odd node 
        if(fast != null)
        {
            slow = slow.next;
        }
        
        slow = reverse(slow);
        fast = head;

        
        while(slow != null)
        {
           if(slow.val != fast.val)
           {
               return false;
           }
            slow =  slow.next;
            fast = fast.next;
        }
        return true;
    }
    
    public ListNode reverse(ListNode head)
    {
        ListNode newHead = null;
        while(head != null)
        {
            ListNode next = head.next;
            head.next = newHead;
            newHead = head;
            head  = next;
        }
        return newHead;
    }
}

Time Complexity : O(n)

Space Complexity: O(1)

Note:

Since I’m interested in problem-solving, so I love to teach others programming in a short and sweet way. To get notification of my future articles like this, follow me via email.

Processing…
Success!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s