Understanding Palindrome Linked List in Java

Introduction & Problem Explanation

The Palindrome Linked List problem asks us to determine if a given singly linked list is a palindrome (i.e., reads the same forwards and backwards).

For example, the list 1 -> 2 -> 2 -> 1 is a palindrome, while the list 1 -> 2 -> 3 is not. The primary constraint is doing this in O(n) time complexity and O(1) space complexity. Since we cannot traverse a singly linked list backwards, this requires a clever combination of list operations.

The Algorithmic Approach

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

We can copy all list values into an ArrayList or push them onto a Stack, and then check for palindrome properties using standard arrays/stack mechanisms. While straightforward, this requires O(n) extra storage space, which violates the strict constant space constraint.

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

We can achieve the result in-place using three main steps:

1. Find the middle of the linked list using the two-pointer **fast and slow** technique (where fast moves twice as fast as slow).
2. Reverse the second half of the linked list starting from the middle node (slow).
3. Compare the values of the first half (starting at head) and the reversed second half (starting at the new head of the reversed portion) node by node.

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

Step-by-Step Execution Walkthrough

Let's trace the algorithm on the linked list 1 -> 2 -> 2 -> 1 -> null:

1. Step 1 (Find Middle):
   • Initialize slow and fast pointers at head (node 1).
   • Iteration 1: slow = 2 (second node), fast = 2 (third node).
   • Iteration 2: slow = 2 (third node), fast = null.
   • The loop terminates since fast is null. The middle of the list is at slow (the third node 2).
2. Step 2 (Reverse Second Half):
   • We call our reverse function on the second half starting at slow: 2 -> 1 -> null.
   • This returns the reversed chain: 1 -> 2 -> null.
3. Step 3 (Compare Halves):
   • Initialize firstHalf = head (node 1) and secondHalf = reversedHead (node 1).
   • Compare node values:
     • Step 3a: firstHalf.val (1) == secondHalf.val (1). Match. Advance pointers.
     • Step 3b: firstHalf.val (2) == secondHalf.val (2). Match. Advance pointers.
   • Since secondHalf reaches null, the comparison finishes successfully.
4. Step 4 (Completion): All elements matched, so the method returns true. The list is confirmed as a palindrome.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }: Classic slow/fast algorithm. When fast reaches the end, slow is guaranteed to be at the middle node of the list.
• ListNode secondHalf = reverseList(slow);: Inverts the second half, allowing us to traverse the second half forward rather than backward.
• if (firstHalf.val != secondHalf.val) return false;: Immediately rejects the list as a palindrome upon detecting the first mismatch.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

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

Solving the Palindrome Linked List problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.