palindrome-linked-list

Difficulty: Easy · Topic: Linked List · Practice it on parikshan: /practice/palindrome-linked-list/start

The story

A DNA sequencer at Illumina streams base pairs as a linked list to keep RAM flat as megabase reads roll in. The bioinformatics pipeline checks each read for palindromic structure (restriction-enzyme motifs, hairpin loops) before the read leaves the streaming buffer. The check must be O(n) time and O(1) extra space; the read can be 250,000 nucleotides and there is no spare memory to copy it.

palindrome-linked-list is the canonical version of that check on a stream you cannot copy. It is also the showpiece of the Linked List toolkit because the optimal solution composes both earlier primitives: middle-of-linked-list finds the split point, and reverse-linked-list reverses the second half. Two patterns, one solution.

What's actually being asked

Given the head of a non-empty singly linked list, return true if the sequence of node values reads the same forward and backward, otherwise false. The target is O(n) time and O(1) extra space, i.e., no copying values into an array.

The naive approach

Walk the list, collecting values into a Python list. Two-pointer compare front and back. O(n) time, O(n) extra space. Trivially correct, but the spec rules out the O(n) space.

A second naive: recursion uses the call stack as a reverse traversal. O(n) time, O(n) stack space. Same space cost wearing a different hat. Also rules out by the spec.

Both pass simple test cases. They fail the parikshan dynamic private tests at the high end of n = 100,000 because the recursion blows the CPython stack and the array version blows the memory budget on stress benchmarks. The spec is explicit about O(1) for a reason.

The key insight

Reduce the problem to "compare the first half against the reverse of the second half". For that you need two things:

A way to find the midpoint in one pass: middle-of-linked-list with slow/fast pointers.
A way to reverse the second half in place: reverse-linked-list with the three-pointer dance.

Once you have those two halves, walk both from their respective heads and compare values pairwise. If any pair differs, return false; if you reach the end of the second (shorter or equal) half, return true.

That is the entire algorithm. Compose the two primitives. This is what the Linked List cluster is structured to teach: you stop solving every linked-list problem from scratch and start composing.

Step-by-step approach

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

def is_palindrome(head):
    if head is None or head.next is None:
        return True                        # 0 and 1 nodes are trivially palindromes

    # Phase 1: find the start of the second half (the slow/fast midpoint).
    slow = fast = head
    while fast.next is not None and fast.next.next is not None:
        slow = slow.next
        fast = fast.next.next
    # For odd n, slow is at the exact middle (which belongs to neither half).
    # For even n, slow is at the last node of the first half.
    # In both cases, slow.next is the head of the second half.

    # Phase 2: reverse the second half in place.
    prev, curr = None, slow.next
    while curr is not None:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # prev is now the new head of the reversed second half.

    # Phase 3: walk first half and reversed second half in lockstep, compare.
    left, right = head, prev
    while right is not None:               # second half is the shorter side
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

Loop invariants:

Phase 1: slow has taken half as many steps as fast; both are inside the list. The loop condition fast.next and fast.next.next is the variant of middle-of-linked-list that lands on the first middle (the last node of the first half on even n), which is what we want for splitting.
Phase 2: identical to reverse-linked-list, applied to the suffix starting at slow.next.
Phase 3: left walks the first half, right walks the reversed second half. Stop on right is None because for odd n the second half is one node shorter (the exact middle is skipped), so the second half is always the safe loop bound.

Note that the original list is mutated. The second half is now pointing backwards. If your caller needs the list intact, reverse the second half again before returning. The parikshan problem does not require restoration; the editorial does mention it as a courtesy.

Worked example

Input: 1 -> 2 -> 3 -> 2 -> 1 (n = 5, palindrome).

Phase 1: slow/fast walk.

slow=1, fast=1.
Iter 1: slow=2, fast=3.
Iter 2: slow=3, fast=1 (last node). fast.next is null → exit.

slow is at node 3 (the middle, odd n). Second half starts at slow.next = 2 (the fourth node).

Phase 2: reverse 2 -> 1. Result: 1 -> 2. prev = 1 (the fifth node, now the head of the reversed second half).

Phase 3: compare.

left=1, right=1. Match. Advance both.
left=2, right=2. Match. Advance both.
left=3, right=null. Loop exits.

Return true. ✓

Counter-case: 1 -> 2 -> 3 -> 4 (n = 4, not a palindrome).

Phase 1: slow=2, fast=4 (last node). fast.next is null → exit. slow is at node 2 (last of first half). Second half head = node 3.

Phase 2: reverse 3 -> 4. Result: 4 -> 3. prev = 4.

Phase 3:

left=1, right=4. Mismatch. Return false. ✓

Complexity

Time: O(n). Three linear passes: midpoint, reverse, compare.
Space: O(1). A handful of pointers, no auxiliary structures.

Common pitfalls

Wrong midpoint convention: using while fast and fast.next (the middle-of-linked-list convention for the second middle) makes slow overshoot by one on even n, and the comparison gets misaligned. The split-friendly convention is while fast.next and fast.next.next, which lands on the first middle.
Forgetting to terminate on right is None: if you loop while both left and right are non-null, an odd-length palindrome still works, but a list like 1 -> 0 -> 1 with an extra trailing zero would let left keep walking past the comparison range. Using right as the bound is the safe convention.
Reversing the whole list: a common over-eager AI move. Reversing the entire list and comparing it to the original requires storing the original somewhere, which costs O(n) space. Reverse only the second half.
Not restoring the list: parikshan does not require it for this problem, but production code might. Add a fourth phase: re-reverse the second half and splice it back to slow.next. The cost is O(n) more pointer writes; the caller's invariants are preserved.

Where this shows up in the enterprise

Illumina / Oxford Nanopore DNA reads: scanning a streaming nucleotide list for palindromic motifs without copying.
Network packet inspection: a linked sequence of bytes from a captured packet checked for symmetric patterns (some intrusion-detection signatures).
Audio fingerprinting at Shazam: looking for symmetric chunks in a linked buffer of audio samples.
Chess engines: checking for symmetric move sequences in a linked list of half-moves.
Compiler IR: checking that a basic block is its own reverse-mirror; useful for some optimisation invariants.
Quantum circuit simulation: a chain of gates checked for palindromic structure as a fast pre-pass before more expensive equivalence checks.

The fingerprint: a stream you cannot copy, a symmetry check, and a tight O(1) extra space budget.

Variants you'll see elsewhere

reorder-list: same midpoint-plus-second-half-reverse skeleton, with a final weave instead of a compare.
palindrome-number: same idea on an integer; reverse the digits and compare. Different data, same insight.
valid-palindrome (string variant): two-pointer compare on indices; no list manipulation.
palindromic-substrings: a completely different (DP) problem despite the name.
is-subsequence: same one-pass two-pointer pattern in a different shape.

How parikshan turns this into a learning loop

This is the problem that locks in the Linked List toolkit. Recommended sequence:

Solve reverse-linked-list and middle-of-linked-list first. If either is not muscle memory, palindrome will feel like three problems instead of one.
In practice mode, AI off, write the three-phase solution. Run public tests.
The dynamic private tests will throw: single node (trivially true), two equal nodes (true), two unequal nodes (false), odd-length palindrome, even-length palindrome, length 100,000 random non-palindrome. The two-node cases are where wrong midpoint conventions die.
Re-solve with the O(n) space array version. Compare. Both are O(n) time; the array version is shorter to write but allocates. Decide when you would accept each.
Ask the parikshan AI to Review for the "restore the list" courtesy. The agent should mention it; if it does not, you have caught the agent skipping the half of the spec that real production code cares about.

In the AI-integrated workspace

Generated palindrome-linked-list code splits cleanly into two camps:

Array-copy: short, correct, O(n) space. The agent will produce this 70% of the time unless explicitly told "O(1) extra space".
Three-phase: correct, O(1) space, ten lines of pointer manipulation. The agent produces this 30% of the time, and gets the midpoint condition wrong half of those.

Verification ritual:

Ask: "what is the extra space complexity?" If "O(n)", insist on the in-place version.
Ask the agent to state the midpoint convention. The split-friendly version is while fast.next and fast.next.next. If the agent uses while fast and fast.next, ask it to trace by hand on [1, 2, 2, 1]. Wrong conventions misalign and the four-node palindrome fails.
Ask: "does this restore the list?" In production, the answer matters. Even if the spec does not demand it, callers usually assume their data structures survive function calls.

The deeper lesson: two primitives compose into a third. Once reverse-linked-list and middle-of-linked-list are reflexes, this problem and reorder-list and sort-list are all the same problem with different final phases. Engineers who think in compositions ship faster and review faster. parikshan's Linked List cluster is sequenced exactly to build that compositional reflex.