Palindrome Linked List
Middle by slow and fast, reverse the second half, compare front against back, reverse it back.
List Pointer Puzzles: A palindrome of odd length
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.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(1)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
List Pointer Puzzles covers these too, in the same run.