Understanding Palindrome Linked List in Java

What We're Solving & Sequential Symmetry

Verifying symmetry across linear data streams is a common task in algorithmic logic. The Palindrome Linked List problem asks us to determine if a given singly linked list reads the same forward and backward.

For example, the list 1 -> 2 -> 2 -> 1 -> null represents a palindrome, whereas the list 1 -> 2 -> 3 -> null does not.

The primary constraint of this problem is to achieve our result in linear O(n) time complexity using only constant O(1) auxiliary space. Because a singly linked list lacks backward pointers, traversing backward is impossible without modification, forcing us to use a creative combination of pointer manipulation techniques.

The Strategy

1. Auxiliary Stack Approach (O(n) Space)

A simple way to verify symmetry is to copy all node values into a list or push them onto a stack. We then read the list or pop values from the stack to verify if they match the original sequence. While simple, this approach requires O(n) extra memory, which violates the strict O(1) space requirement.

2. Middle Reversal Optimization (O(n) Time, O(1) Space)

We can solve the problem in-place using three coordinated phases:

• Find the Middle: We use the two-pointer fast and slow technique (where fast moves at double the speed of slow). By the time fast reaches the end of the list, slow is guaranteed to be at the middle node.
• Reverse the Second Half: We reverse the entire second half of the list starting from the slow node.
• Compare Halves: We initialize two pointers: one at the start of the first half (head) and one at the head of the reversed second half. We compare their values node-by-node. If any values mismatch, the list is not a palindrome.

After checking, we can optionally reverse the second half again to restore the original list structure. This runs in linear O(n) time using only O(1) memory.

Detailed Trace Walkthrough

Let's trace this middle reversal algorithm step-by-step on 1 -> 2 -> 2 -> 1 -> null:

1. Step 1 (Locate Middle):
   • Initialize slow and fast pointers at head (node 1).
   • Iteration 1: slow advances to the second node 2; fast advances two steps to the third node 2.
   • Iteration 2: slow advances to the third node 2; fast advances to null.
   • The loop terminates. The middle of the list is at slow (the third node 2).
2. Step 2 (Reverse Second Half):
   • We call our list reversal helper on the second half starting at slow (2 -> 1 -> null).
   • The helper returns the reversed chain: 1 -> 2 -> null.
3. Step 3 (Compare Halves):
   • Set firstHalf = head (node 1) and secondHalf to the reversed head (node 1).
   • Compare values:
     • Step 3a: firstHalf.val (1) == secondHalf.val (1). Match. Advance pointers: firstHalf becomes node 2, secondHalf becomes node 2.
     • Step 3b: firstHalf.val (2) == secondHalf.val (2). Match. Advance pointers: secondHalf becomes null.
   • Since secondHalf is null, the verification completes successfully.
4. Step 4 (Completion): All compared values matched, so the method returns true.

Code Highlights & Explanations

Key sections of our Java implementation:

• while (fast != null && fast.next != null) ensures correct slow/fast pointer traversal for both even and odd length lists.
• reverseList(slow) inverts the link directions of the second half of the list in-place.
• firstHalf.val != secondHalf.val provides an early exit, returning false as soon as a mismatch is detected.

Full Code Solution

Below is the complete, self-contained Java source code that solves this problem, featuring in-place middle reversal and comparison, along with a main test runner.

package io.practise.dsa;
 
public class PalindromeLinkedList {
 
    public static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val) { this.val = val; }
    }
 
    // Optimized - Reverse 2nd Half + Compare - O(n)
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        
        // Find middle
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Reverse second half
        ListNode secondHalf = reverseList(slow);
        
        // Compare both halves
        ListNode firstHalf = head;
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) return false;
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }
        return true;
    }
 
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
 
    public static void main(String[] args) {
        PalindromeLinkedList solver = new PalindromeLinkedList();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(1);
 
        System.out.println("--- Palindrome Linked List Demonstration ---");
        System.out.println("Is Palindrome: " + solver.isPalindrome(head));
    }
}

Conclusion & Takeaways

Checking linked list symmetry in constant space highlights the utility of multi-pointer coordination and temporary link reversals. By finding the middle node, reversing the second half, and sweeping forward, we avoid auxiliary storage arrays and solve the problem in a single linear pass.