Pattern visualizer
Reorder List
The target order interleaves the first half read forward with the second half read backward, but a singly linked list has no way to walk backward, so the second half must actually be reversed before anything can be spliced. Fast and slow pointers find the midpoint in one pass: fast covers two nodes for every one slow covers, so fast hits the end exactly when slow is at the middle. Cutting the list there gives two independent chains; reversing the second one in place turns it into last-to-first order. From there, splicing alternates a node from the first chain with a node from the reversed second chain, always saving both next pointers before either is overwritten. The first half is never shorter than the second, so the loop can end the moment the second chain runs out. Animated on: list = [1, 2, 3, 4, 5]. Reorder in place so it reads first[0], last[0], first[1], last[1], ... — L0 -> Ln -> L1 -> Ln-1 -> ... Answer: [1, 5, 2, 4, 3]..
Find the middle, reverse the back half, splice the two together
list = [1, 2, 3, 4, 5]. The target order zips the first half forward with the second half backward, which a singly linked list can't read off directly — the split point has to be found first. slow and fast both start at the head; fast moves two nodes for every one slow moves, so when fast runs out of room slow is sitting exactly at the midpoint.
1FUNCTION reorderList(head)2 slow <- head, fast <- head3 WHILE fast.next != NULL AND fast.next.next != NULL4 slow <- slow.next5 fast <- fast.next.next6 second <- REVERSE(slow.next)7 slow.next <- NULL8 first <- head9 WHILE second != NULL10 tmp1 <- first.next11 tmp2 <- second.next12 first.next <- second, second.next <- tmp113 first <- tmp1, second <- tmp214 RETURN head
← / → step · space play · Home restart