AlgoScope

Reorder List

Middle by slow and fast, reverse the second half, weave first and second alternately.

Linked list algorithms, algorithm, intermediate
Middle at 4.1234567headslowfast
Middle at 4.1234567headslowfast

Rewiring a List: Reorder first, last, second, ...

Decision, step 2 of 10

Slow moves one node for every two of fast. Fast stops at 7, so slow is at 4: the first half is 1, 2, 3, 4, the second 5, 6, 7.

How rewiring a list works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Taught by the same lesson

Rewiring a List covers these too, in the same run.