AlgoScope

Palindrome Linked List

Middle by slow and fast, reverse the second half, compare front against back, reverse it back.

Linked list algorithms, algorithm, intermediate
Second half starts at 3.12321headslowfast
Second half starts at 3.12321headslowfast

List Pointer Puzzles: A palindrome of odd length

Decision, step 2 of 10

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)

Leads to

Topics that need this one first.

Taught by the same lesson

List Pointer Puzzles covers these too, in the same run.