Palindrome Linked List

Solution

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

 

 

Examples

Example 1:

Input: head = [1,2,2,1]
Output: true

 

Example 2:

Input: head = [1,2]
Output: false

 

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

 

Explanation

class Solution {
    public boolean isPalindrome(ListNode head) {
    	// Find the middle ListNode
        ListNode slow = head, fast = head, prev, temp;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

	// Reverse the Half list
        prev = slow;
        slow = slow.next;
        prev.next = null;
        while(slow != null){
            temp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = temp;
        }
        
        // Iterate over two pointers, one starting from the first element 
        // and the other from the last, moving inward while checking if the values match
        fast = head;
        slow = prev;
        while(slow != null){
            if(fast.val != slow.val) return false;
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
                                        
}

 

1. Find the middle in the given ListNode

We use the two-pointer technique to find the middle of the linked list. One pointer, fast, moves twice as fast as the other, slow. When fast reaches the end of the list (i.e., fast or fast.next is null), the slow pointer will be at the middle of the list. If the number of nodes is even, slow will point to the second half of the list (after the middle node).

 

2. Reverse the Half of the list

After finding the middle of the list, we reverse the second half. This is crucial because to check if the linked list is a palindrome, we need to compare the first half of the list with the reversed second half. Since singly linked lists do not allow backward traversal, reversing the second half of the list makes it easier to compare the two halves.

 

For example, for the list [1, 2, 4, 4, 2, 1], after finding the middle and reversing the second half [4, 2, 1], the list becomes [1, 2, 4] and [1, 2, 4], which can then be compared node by node

 

3. Check if values match

Now, with two pointers, one starting from the head of the list (the first element) and the other starting from the reversed second half, we move inward, comparing the values of the nodes. If at any point the values don’t match, return false. If all values match, return true, indicating that the list is a palindrome.