Does a chain read the same backwards?

Linked lists Mid-level Python 3.13+ Reviewed By Best Latest Apps

Pick the fix

Your O(1)-memory version passes all tests but a teammate's code breaks after calling it. Why?

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A It leaves the second half turned around; turn it back before returning

Right: the caller's chain is now cut in half.

In-place tricks change shared data, so restoring it (or documenting it) is part of a complete answer.

Why not the others?
  • B The slow pointer is too slow. Speed affects time, not the caller's data.
  • C Python lists are immutable. They are not, and no list is involved here.

30-second answer

Find the middle with slow and fast pointers, turn the second half around, then compare the halves link by link. O(n) time and O(1) memory. Turning the second half back afterwards restores the input, which is polite if the caller still needs it.

Practise saying it · 45 s. No recording, just a timer

Explain checking a chain reads the same backwards.

Say your answer out loud, then check which of these points you covered:

  • Find the middle
  • Turn the second half
  • Compare and restore

Deep dive

Copying values into a list and comparing with its reverse is O(n) memory and a fine first answer.

For odd lengths, the middle link can be ignored.

Mention restoring the chain; mutating input silently is a code-review issue.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def reads_same(head: Link | None) -> bool:
    slow = fast = head
    # fast moves two links per step, slow one
    while fast and fast.next:
        slow = slow.next if slow else None
        fast = fast.next.next
    back: Link | None = None
    while slow is not None:  # turn the second half around
        slow.next, back, slow = back, slow, slow.next
    left, right = head, back
    while right is not None and left is not None:
        if left.val != right.val:
            return False
        left, right = left.next, right.next
    return True

Common mistakes

  • Comparing the full first half with a half that is one link shorter, then failing on odd lengths.
  • Leaving the input chain modified without saying so.

Senior take & follow-ups

Offer the list version first, then improve the memory; that shows a clear path.

Follow-up questions

Think of your answer first, then open the hint.

  1. Can you do it without modifying the chain?

    Show hint

    Only with O(n) memory (a list or a recursion stack).

  2. What about a doubly linked chain?

    Show hint

    Walk inward from both ends; O(1) memory and no modification.

What each operation costs: Linked List · Singly Linked List · Doubly Linked List

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.