Reorder List
Find the middle, reverse the back half, splice the two together
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.
Details
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].
Problem:Reorder ListMedium
Find the middle, reverse the back half, splice the two together
step 1 / 11
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.
- slow=0· arr[0] = 1
- fast=0· arr[0] = 1
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
Every step in words
Show all 11 steps
- 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.
- slow steps to 2 (index 1), fast jumps to 3 (index 2) — fast still has two more nodes ahead, so the walk continues.
- slow steps to 3 (index 2), fast jumps to 5 (index 4). fast cannot take a full two-node hop from here, so the loop stops: 3 is the midpoint, splitting the list into a first half of 3 node(s) and a second half of 2 node(s).
- secondHead <- slow.next = 4 (index 3), then slow.next <- NULL cuts the list into two independent chains: first half [1, 2, 3] stays put, second half [4, 5] is about to be reversed.
- Reverse the second half in place: prev <- NULL, cur <- 4 (index 3). This is the same three-pointer relinking as reversing a whole list, just scoped to the detached second chain.
- 4.next <- NULL reverses that one link; prev advances to 4 (index 3), cur advances to 5 (index 4).
- 5.next <- 4 reverses the last link; cur is now NULL so the loop stops. The reversed second half reads [5, 4] starting from prev = 5.
- Merge begins: first <- head (1, index 0), second <- the reversed second half (5, index 4). Splice one node from first, then one from second, until second runs out — the first half is never shorter, so it can't run out before second does.
- 1.next <- 5, then 5.next <- 2 splices 5 in right after 1. first advances to 2, second advances to 4.
- 2.next <- 4, then 4.next <- 3 splices 4 in right after 2. first advances to 3, second is now NULL so the loop stops.
- second is NULL, merge complete. Reading next pointers from head gives [1, 5, 2, 4, 3] — first half forward interleaved with second half backward. Finding the middle, reversing in place, and splicing costs O(n) time and O(1) extra space, versus buffering every node into an array first.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.