LeetCode 234 · Linked list

Palindrome Linked List, explained with a picture

Folding a train in half.

Linked list
▶ Watch it step by step

The problem

Decide whether a linked list reads the same forwards and backwards (a palindrome).

Input:  1 → 2 → 3 → 2 → 1
Output: true

Picture it

Picture folding the train in half. Find the middle with tortoise and hare, reverse the back half, then compare the two halves coach by coach from the outside in.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Middle + reverse second half + compare. O(n) time, O(1) space.

Python solution

def is_palindrome(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    prev = None
    while slow:
        slow.next, prev, slow = prev, slow, slow.next
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left, right = left.next, right.next
    return True

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.