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 TrueIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.