Palindrome Linked List — Split, Reverse, Compare in O(1) Space

Problem Statement#

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

Constraints:

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

Example 1:

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

Example 2:

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

Example 3:

Input:  head = [1]
Output: true
Explanation: A single node is trivially a palindrome.

Why This Problem Matters#

Palindrome Linked List (LeetCode 234) is the problem that combines three separate linked list techniques into one solution. Facebook (Meta), Amazon, and Apple ask it specifically because it's a composite problem — you can't solve it with one trick alone. You need to know fast/slow pointers, list reversal, and two-pointer comparison, and you need to compose them in the right order. That composition skill is exactly what senior engineers are evaluated on.

The naive approach — copy values to an array and use two pointers from both ends — works in O(n) time but O(n) space. The follow-up is always: "Can you do it in O(1) space?" This is where the problem becomes interesting. The O(1) solution requires you to mutate the input list (reversing the second half in place), which raises questions about when mutation is acceptable and how to restore the original structure if needed.

The problem also appears as a real engineering pattern. Checking whether a sequence is symmetric without buffering it appears in stream processing, cryptographic hash comparisons, and data integrity checks. Understanding the O(1) space approach shows you think about memory efficiency — a trait valued in embedded systems, mobile, and high-performance computing.

The Core Insight#

A palindrome reads the same forwards and backwards. For a linked list, you can't traverse backwards — so the insight is to reverse the second half of the list in place and then compare the first half (left pointer moving right) against the reversed second half (right pointer moving through the reversed portion).

The three-phase algorithm:

1. Find the middle — use fast/slow pointers. When fast reaches the end, slow is at the midpoint.
2. Reverse the second half — apply the standard iterative reversal from slow's next onward.
3. Compare — two pointers, one from the original head, one from the new head of the reversed half.

The elegant property: you don't need to know the list length. The fast/slow split naturally handles both odd-length and even-length lists.

Visual Dry Run#

Input: 1 -> 2 -> 2 -> 1

Phase 1: Find middle

slow is at the second 2 (index 2). The midpoint is the node at index 1 (value 2).

Actually, with while fast and fast.next, slow stops at index 1 (value 2):

Now fast.next is 1 (idx 3), fast.next.next is None — loop continues:

| 2 | 2 (idx 2) | 1 (idx 3) |

Now fast.next is None — loop stops. slow is at index 2 (value 2).

Phase 2: Reverse second half starting from slow.next (index 3, value 1)

Reversal of [1] is just [1]. prev = 1 (idx 3).

Cut: slow.next = None — first half is 1 -> 2 -> 2.

Phase 3: Compare

left = 1 (idx 0), right = 1 (idx 3, reversed head)

Right exhausted — return true.

Odd-length example: 1 -> 2 -> 1

After fast/slow: slow lands at index 1 (value 2). Second half reversed: 1 (idx 2). Compare 1 (idx 0) vs 1 (idx 2) — match. The middle element (2) is never compared — correct behavior.

Solution (Optimal)#

Python#

def isPalindrome(head):
    # Phase 1: Find the end of the first half
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
    # Phase 2: Reverse the second half
    prev = None
    curr = slow
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # prev is now the head of the reversed second half
 
    # Phase 3: Compare first half and reversed second half
    left = head
    right = prev
    while right:               # second half is shorter or equal
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
 
    return True

Time complexity: O(n) — three linear passes.

Space complexity: O(1) — only pointer variables.

JavaScript#

var isPalindrome = function(head) {
    // Phase 1: Find midpoint
    let slow = head, fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
 
    // Phase 2: Reverse second half
    let prev = null, curr = slow;
    while (curr !== null) {
        const nxt = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nxt;
    }
 
    // Phase 3: Compare
    let left = head, right = prev;
    while (right !== null) {
        if (left.val !== right.val) return false;
        left = left.next;
        right = right.next;
    }
 
    return true;
};

Complexity:

Simple O(n) space approach (if O(1) not required):

def isPalindrome(head):
    vals = []
    while head:
        vals.append(head.val)
        head = head.next
    return vals == vals[::-1]

Common Mistakes#

1. Using while fast and fast.next vs while fast.next and fast.next.next. These two conditions give different midpoints for even-length lists. The former (fast and fast.next) works correctly for this problem — test your choice on both [1,2,2,1] and [1,2,3,2,1] before coding.

2. Not cutting the first half from the second. After finding the midpoint, you must set slow.next = None (or begin reversal from slow.next) so the first half properly terminates. Without this cut, the reversed second half still connects back to the first half, causing infinite loops in the comparison phase.

3. Comparing until left is exhausted instead of right. The second half may be shorter (for odd-length lists, the middle element is in the first half). Drive the comparison loop with while right, not while left. Driving with left would compare extra elements not in the second half.

4. Forgetting to restore the list. If the problem or interviewer asks that you not modify the input, you need a restore phase: reverse the second half again after comparison. Add this after the comparison loop for clean code.

5. Using a stack instead of in-place reversal. Pushing the second half onto a stack is O(n) space — correct but not optimal. Interviewers will ask you to eliminate it.

Interview Tips#

1. Lead with the plan: "I'll split the problem into three phases: find the middle with fast/slow pointers, reverse the second half in place, then compare using two pointers."

2. Draw a picture — palindrome problems are highly visual. Sketch the list, mark the midpoint, show the reversal arrows.

3. Test odd and even lengths — both during your explanation and after coding. [1,2,1] and [1,2,2,1] are the minimal test cases.

4. Mention the restoration option — "If we need to preserve the original structure, we can reverse the second half back after comparison. Should I include that?"

5. Know the naive approach — stating it first shows systematic thinking: "The simple solution copies values to an array in O(n) space. The O(1) solution..."

Follow-up Questions#

Q: Can you do it in O(1) space without modifying the input? Not easily on a singly linked list. You'd need the caller to use a doubly linked list, or you'd need O(n) auxiliary space. On a singly linked list, O(1) space requires in-place reversal (mutation).

Q: What if the list values are not digits but arbitrary objects? The comparison changes from == on integers to .equals() or a custom comparator. The pointer technique remains identical.

Q: What if the list can be a doubly linked list? A doubly linked list has a prev pointer, so you could walk from the tail backward without reversing. That simplifies Phase 2 and 3 but requires a doubly linked list structure.

Q: How does this differ from checking a string palindrome? String palindrome uses two pointers from both ends simultaneously — O(n/2) comparisons. Linked list palindrome can't do that (no random access to the end), so it requires the three-phase approach.

Q: What is the time complexity if we use a recursive approach? A recursive approach that compares the outermost characters via the call stack is O(n) time but O(n) space due to the stack. It is elegant but not space-optimal.

Key Takeaways#

• Palindrome Linked List combines three patterns: fast/slow midpoint, iterative reversal, two-pointer comparison — compose them in order.
• The O(1) space solution requires mutating the list (reversing the second half) — clarify with the interviewer if restoration is needed.
• Drive the comparison loop with while right (not while left) to correctly handle odd-length lists.
• After reversal, prev is the head of the reversed second half — use it as the right pointer.
• The naive O(n) space approach (copy to array) is worth mentioning but not worth submitting if the interviewer wants O(1) space.
• Test your midpoint logic on both even-length and odd-length examples before submitting.