L10: Check if a LinkedList is Palindrome or Not | Multiple Approaches

1. Problem Statement & Definition of a Palindrome

A palindrome is a sequence that reads the same forwards and backwards. For instance, the string "mom" spelled in reverse is still "mom".

When dealing with a Singly Linked List, checking for a palindrome is not as trivial as simply reading characters from both ends. Because a singly linked list only maintains pointers moving in the forward direction (next), we cannot instantly access the last node from the head.

• Odd Length Linked List Example: 1 -> 2 -> 3 -> 2 -> 1 -> null Comparing elements symmetrically from the outer edges inward yields identical pairs (1 == 1, 2 == 2, and the middle element 3). This is a palindrome.
• Even Length Linked List Example: 1 -> 2 -> 3 -> 3 -> 2 -> 1 -> null Symmetrical outer-to-inner comparisons match across all positions. This is also a palindrome.
• Non-Palindrome Example: 1 -> 2 -> 3 -> 2 -> 3 -> null Comparing the final elements fails (3 != 2), so it returns false.

2. Approach 1: The Naive Stack-Based Solution (Using Extra Space)

Core Mental Model

If we need to inspect elements in reverse order without backward pointers, we can use an auxiliary data structure that naturally reverses order: a Stack. A Stack operates on a Last-In, First-Out (LIFO) principle.

Step-by-Step Algorithm

1. Initialize: Create an empty stack and set a temporary pointer (temp) to the head of the linked list.
2. Phase 1 (Push): Traverse the entire linked list from head to tail. For every node encountered, push its data onto the stack, then advance temp.
3. Phase 2 (Compare): Reset temp back to point to the head of the linked list. Traverse the linked list a second time while simultaneously popping elements off the stack.
4. Validation: Compare each node's data with stack.top(). If any value does not match, immediately return false. If the traversal completes successfully without mismatches, return true.

Java-Style Conceptual Code

public boolean isPalindromeStack(ListNode head) {
    if (head == null || head.next == null) return true;
    
    Stack<Integer> stack = new Stack<>();
    ListNode temp = head;
    
    // Phase 1: Push all elements onto the stack
    while (temp != null) {
        stack.push(temp.val);
        temp = temp.next;
    }
    
    // Phase 2: Traverse again and compare with stack top
    temp = head;
    while (temp != null) {
        if (temp.val != stack.peek()) {
            return false;
        }
        stack.pop();
        temp = temp.next;
    }
    
    return true;
}

Complexity Analysis

• Time Complexity: $O(2N) \approx O(N)$ because we traverse the linked list twice (once for pushing, once for comparing).
• Space Complexity: $O(N)$ because every single node's value is duplicated and stored inside an external stack.

Note: Interviewers will typically reject this solution because of the $O(N)$ extra space complexity, prompting you to optimize it down to $O(1)$ auxiliary space.

3. The Optimal Approach: In-Place Link Manipulation

To solve this problem in $O(1)$ auxiliary space, we cannot use external data structures. Instead, we must rearrange pointers directly within the given linked list.

High-Level Strategy

1. Find the middle of the linked list using the Tortoise and Hare (Slow and Fast pointer) algorithm.
2. Reverse the second half of the linked list starting from the node right after the middle.
3. Compare the nodes of the first half and the reversed second half head-to-head.
4. Restore (Re-reverse) the second half back to its original configuration before returning the result, ensuring we preserve the input data structure integrity.

4. Step 1: Finding the Middle (Tortoise and Hare Algorithm)

We use two pointers: slow and fast, both starting at the head.

• slow moves 1 step at a time: slow = slow.next
• fast moves 2 steps at a time: fast = fast.next.next

Handling Even vs. Odd Lengths

Depending on whether the list length is even or odd, we need slow to land precisely on the middle-1 node (for even lists) or the exact middle node (for odd lists) so that we can isolate the second half correctly.

• Even Length Stop Condition: Stop when fast.next.next == null. slow will rest on the last node of the first half.
• Odd Length Stop Condition: Stop when fast.next == null. slow will rest on the exact center node.

ListNode slow = head;
ListNode fast = head;

while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// 'slow' now points to the end of the first half

5. Step 2: Reversing the Second Half

Once slow identifies the split point, the head of the second half is located at slow.next. We pass slow.next into a standard linked list reversal function.

Real-World Analogy & Mechanism

Think of reversing a train track segment: we detach the couplings between nodes in the second half and point each node's next pointer backward toward its predecessor. The node right after slow becomes the new head of the reversed sub-list.

// Helper function to reverse a linked list
public ListNode reverse(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextNode = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextNode;
    }
    return prev;
}

// Execution in palindrome check:
ListNode newHead = reverse(slow.next);

6. Step 3: Comparative Walkthrough & Node Inspection

With the second half reversed, we set up two traversal pointers:

• first: Points to the beginning of the list (head).
• second: Points to the beginning of the reversed sub-list (newHead).

We walk both pointers forward in lockstep, comparing their values.

7. Step 4: Restoring the List (Crucial Interview Requirement)

Professional software engineering standards require that input data structures remain unmodified unless specified otherwise. If our function exits early or successfully after verification, leaving the second half reversed will break external references holding onto that linked list.

Therefore, before returning true or false, we must call reverse(newHead) once more to restore the original links.

8. Comprehensive Code Implementation

Below is the complete, production-ready Java implementation combining all phases with edge case handling:

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class PalindromeLinkedList {

    public boolean isPalindrome(ListNode head) {
        // Edge Case: 0 or 1 node is always a palindrome
        if (head == null || head.next == null) {
            return true;
        }

        // Step 1: Find the middle node using Slow and Fast pointers
        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Step 2: Reverse the second half of the linked list
        ListNode newHead = reverse(slow.next);

        // Step 3: Set up pointers for comparison
        ListNode first = head;
        ListNode second = newHead;
        boolean result = true;

        while (second != null) {
            if (first.val != second.val) {
                result = false;
                break;
            }
            first = first.next;
            second = second.next;
        }

        // Step 4: Restore the linked list (Re-reverse the second half back)
        slow.next = reverse(newHead);

        return result;
    }

    // Helper method to reverse a linked list
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        return prev;
    }
}

9. Complexity Analysis Summary

10. Summary and Key Takeaways

• Definition of Palindrome: A structure whose reverse sequence mirrors its forward sequence identically.
• Limitation of Singly Linked Lists: Lack of backward (prev) pointers means we cannot traverse backwards directly from the tail.
• Naive Trade-offs: Stacking elements into an external data structure provides an intuitive solution at the cost of $O(N)$ extra memory.
• Optimal Strategy: Splitting the list in half, reversing the trailing segment, and performing parallel comparisons achieves $O(1)$ auxiliary space complexity.
• The Tortoise and Hare Pattern: Essential for finding the exact midpoint (slow) and stopping safely based on even/odd length node constraints.
• Data Integrity / Cleanup: Always restore modified pointers (re-reversing the second half) prior to returning from the function to prevent side-effects in production environments.