Palindrome Linked List
Middle by slow and fast, reverse the second half, compare front against back, reverse it back.
Slow takes one step for every two of fast. When fast runs out, slow is at 3, the start of the second half, which includes the middle node; comparing it with itself is harmless.
What you will see
Second half flips; two pointers compare node by node from both ends.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(1) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Each node announces its value and what it points to; each step announces the pointer change ("node 3 now points to node 5").
Reduced motion: Pointer arrows redraw in place with a brief emphasis instead of animating the detach and reattach.
Before this
Taught by the same lesson
List Pointer Puzzles covers these too, in the same run.