How to Detect if a Linked List Is a Palindrome: Two Optimal Approaches

You can detect if a linked list is a palindrome in O(N) time by either using recursion to simulate a stack (O(N) space) or using a fast/slow pointer to find the middle and reversing the second half in place (O(1) space).

Unlike arrays or strings, a singly-linked list cannot be traversed backwards, which prevents the classic two-pointer technique from working directly. According to the labuladong/fucking-algorithm repository, specifically the tutorial in 高频面试系列/判断回文链表.md, there are two robust strategies that overcome this limitation while maintaining linear time complexity.

Why the Standard Two-Pointer Technique Fails

In a singly-linked list, each node only stores a reference to the next node. This means you cannot start one pointer at the head and another at the tail and move them toward the center. Any solution must either use extra space to store the values (or nodes) in reverse order, or temporarily modify the list structure to allow backward traversal.

Method 1: Recursive Stack Simulation (O(N) Time, O(N) Space)

This approach leverages the program call stack to implicitly reverse the list. As explained in lines 121-151 of 高频面试系列/判断回文链表.md, the algorithm uses post-order traversal to compare nodes from the outside in.

How It Works

The recursion first reaches the tail of the list (the base case). As the stack unwinds, each recursive call holds a reference to a node from the second half of the list (right), while a global pointer (left) starts at the head and moves forward. The algorithm compares left.val with right.val at each unwinding step. If any pair differs, the list is not a palindrome.

Implementation Details

The solution requires a class-level variable left to track the front of the list and a boolean res to store the result. The traverse method implements the post-order logic: it recurses on right.next first, then performs the comparison, then advances left.

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def __init__(self):
        self.left = None
        self.is_pal = True

    def isPalindrome(self, head: ListNode) -> bool:
        self.left = head
        self._traverse(head)
        return self.is_pal

    def _traverse(self, right: ListNode):
        if not right:
            return
        self._traverse(right.next)          # reach the tail first

        if self.left.val != right.val:      # compare mirrored nodes

            self.is_pal = False
        self.left = self.left.next          # advance left pointer

This method is conceptually identical to pushing all nodes onto an explicit stack and then popping them to compare with the original list, but it uses the system's call stack instead of auxiliary data structures.

Method 2: Fast/Slow Pointer with In-Place Reversal (O(N) Time, O(1) Space)

For scenarios where space is constrained, the optimal solution uses the fast/slow pointer technique to find the middle of the list, then reverses the second half in place. This allows you to compare the first half with the reversed second half using two forward-moving pointers. As documented in lines 168-199 of 高频面试系列/判断回文链表.md, this approach achieves O(1) extra space complexity.

Step-by-Step Algorithm

1. Locate the midpoint: Initialize slow and fast at the head. Move fast two steps and slow one step per iteration. When fast reaches the end, slow points to the start of the second half.
2. Handle odd length: If fast is not null (odd number of nodes), move slow one step forward to skip the exact middle node.
3. Reverse the second half: Reverse the sub-list starting at slow using a standard iterative reversal.
4. Compare both halves: Initialize left at the head and right at the new head of the reversed half. Walk both pointers simultaneously, comparing values.
5. Restore the list (optional): Reverse the second half again to restore the original structure.

Implementation Details

The reverse helper function uses three pointers (prev, node, nxt) to flip the next references iteratively. The main isPalindrome method orchestrates the pointer movements and comparison logic.

class ListNode {
    int val;
    ListNode next;
    ListNode(int v) { val = v; }
}

class Solution {
    // Checks if the linked list is a palindrome.
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;

        // 1. Find the middle (slow will point to start of second half)
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. Skip the middle node for odd length lists
        if (fast != null) { // odd number of nodes
            slow = slow.next;
        }

        // 3. Reverse the second half
        ListNode right = reverse(slow);
        ListNode left = head;

        // 4. Compare both halves
        while (right != null) {
            if (left.val != right.val) return false;
            left = left.next;
            right = right.next;
        }

        // (Optional) 5. Restore the original list order by reversing again
        // reverse(slow);

        return true;
    }

    // Helper: reverses a singly‑linked list and returns the new head
    private ListNode reverse(ListNode node) {
        ListNode prev = null;
        while (node != null) {
            ListNode nxt = node.next;
            node.next = prev;
            prev = node;
            node = nxt;
        }
        return prev;
    }
}

This approach is preferred in production code and technical interviews when the problem constraints require O(1) auxiliary space, as it only uses a constant number of pointer variables regardless of list length.

Summary

• Singly-linked lists cannot be traversed backwards, preventing the standard two-pointer palindrome check used for arrays.
• Recursive stack simulation achieves O(N) time by using the call stack to reverse the list implicitly, requiring O(N) space. This is implemented in 高频面试系列/判断回文链表.md lines 121-151.
• Fast/slow pointer with in-place reversal achieves optimal O(N) time and O(1) space by finding the middle, reversing the second half, comparing, and optionally restoring the list. This is detailed in lines 168-199 of the same file.
• Both solutions rely on the symmetry property of palindromes: the first half must mirror the second half exactly.

Frequently Asked Questions

Can I solve this by converting the linked list to an array?

Yes, you can traverse the list once to copy values into an array or ArrayList, then use standard two-pointer techniques on the array. This approach runs in O(N) time but requires O(N) extra space for the array, making it less optimal than the in-place reversal method for space-constrained environments.

Why not just use a stack explicitly instead of recursion?

An explicit stack data structure works perfectly well and follows the same logic as the recursive approach: push all nodes onto the stack, then pop and compare with the original list. However, the recursive solution is often more concise in languages like Python, while the explicit stack version requires additional boilerplate to manage the data structure. Both use O(N) auxiliary space.

Does the fast/slow pointer method modify the original list permanently?

The algorithm temporarily reverses the second half of the list to enable the comparison, which does modify the next pointers. However, as shown in the Java implementation, you can restore the original order by reversing the second half a second time after the comparison is complete. If you omit this restoration step, the list will remain modified (reversed in the second half).

What is the time complexity of the recursive approach?

The recursive approach runs in O(N) time because it visits each node exactly twice: once during the forward recursion to reach the tail, and once during the unwinding phase to perform comparisons. The space complexity is also O(N) due to the call stack depth equaling the length of the list.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}