-
Notifications
You must be signed in to change notification settings - Fork 0
067 — Reorder List
LeetCode 143 · Medium. You are given the head of a singly linked list. Reorder the list in place so that if it was originally L0 -> L1 -> ... -> Ln-1 -> Ln, it becomes L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> .... You may not modify the values in the list's nodes; only the nodes themselves may be changed.
Picture a deck of cards laid out in a single row, and you want to interleave it so the first card is followed by the last card, then the second card, then the second-to-last card, and so on — zig-zagging inward from both ends toward the middle. If this were an array, you'd just grab a pointer at each end and walk them toward each other. But it's a singly linked list — there's no "pointer at the end" you can just jump to, and no walking backward once you're past a node. So you need to first find the middle (splitting the deck into a front half and a back half), flip the back half around so its last card becomes first, and then do the zig-zag weave — front half and reversed back half, alternating one node at a time.
This one doesn't match a single pattern cleanly — it's a genuine composition of two patterns, and recognizing that is the cue itself. "Reorder"/"zig-zag from both ends" on a singly linked list screams Two Pointers, but you can't two-pointer from both ends of a singly linked list directly (no backward walking). That forces a first step: Fast and Slow Pointers to find the middle in one pass. Only after the list is split and the second half is reversed does the Two Pointers merge-by-alternating step become possible. Seeing "reorder a linked list by interleaving front and back" should immediately suggest this two-stage pipeline, not a single trick.
Collect every node into an array (random access by index, unlike the list itself), then relink using two indices walking from both ends inward.
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) { self.val = val }
}
func reorderListBruteForce(_ head: ListNode?) {
var nodes: [ListNode] = []
var curr = head
while let node = curr {
nodes.append(node)
curr = node.next
}
guard nodes.count > 1 else { return }
var left = 0
var right = nodes.count - 1
while left < right {
nodes[left].next = nodes[right]
left += 1
if left == right { break }
nodes[right].next = nodes[left]
right -= 1
}
nodes[left].next = nil
}
// smoke test: 1 -> 2 -> 3 -> 4 -> 5
let bn1 = ListNode(1); let bn2 = ListNode(2); let bn3 = ListNode(3); let bn4 = ListNode(4); let bn5 = ListNode(5)
bn1.next = bn2; bn2.next = bn3; bn3.next = bn4; bn4.next = bn5
reorderListBruteForce(bn1)
var bfWalk: ListNode? = bn1
while let n = bfWalk { print(n.val, terminator: " "); bfWalk = n.next } // 1 5 2 4 3Big-O: O(n) time — one pass to collect, one pass to relink. O(n) extra space for the array of node references.
Three stages, each O(n), none using extra data-structure space: find the middle with fast/slow pointers, reverse the second half in place, then merge the two halves alternately.
func reorderList(_ head: ListNode?) {
guard let head = head, head.next != nil else { return }
// 1. Find the middle — slow ends on the last node of the first half.
var slow: ListNode? = head
var fast: ListNode? = head
while fast?.next != nil && fast?.next?.next != nil {
slow = slow?.next
fast = fast?.next?.next
}
// 2. Cut the list in two, then reverse the second half.
var prev: ListNode? = nil
var curr = slow?.next
slow?.next = nil
while curr != nil {
let nextTemp = curr?.next
curr?.next = prev
prev = curr
curr = nextTemp
}
// prev now heads the reversed second half.
// 3. Merge the first half and reversed second half, alternating nodes.
var first: ListNode? = head
var second = prev
while second != nil {
let firstNext = first?.next
let secondNext = second?.next
first?.next = second
second?.next = firstNext
first = firstNext
second = secondNext
}
}
// smoke test: 1 -> 2 -> 3 -> 4 -> 5
let n1 = ListNode(1); let n2 = ListNode(2); let n3 = ListNode(3); let n4 = ListNode(4); let n5 = ListNode(5)
n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n5
reorderList(n1)
var walk: ListNode? = n1
while let n = walk { print(n.val, terminator: " "); walk = n.next } // 1 5 2 4 3
// smoke test: 1 -> 2 -> 3 -> 4 (even length)
let e1 = ListNode(1); let e2 = ListNode(2); let e3 = ListNode(3); let e4 = ListNode(4)
e1.next = e2; e2.next = e3; e3.next = e4
reorderList(e1)
var ewalk: ListNode? = e1
while let n = ewalk { print(n.val, terminator: " "); ewalk = n.next } // 1 4 2 3Big-O: O(n) time — three passes, each linear, so still O(n) overall. O(1) extra space — only a handful of pointer variables, no array.
You can't do a from-both-ends interleave on a singly linked list the way you would on an array, because there's no O(1) access to "the last node" or any walking backward. The fix is to manufacture that capability: find the midpoint with fast/slow pointers (the fast pointer covers two steps for every one of the slow pointer's, so when fast runs out, slow is sitting at the middle), physically reverse the second half so its tail becomes its head, and now both halves can be walked forward-only — which is exactly what Two Pointers needs. The composition of Fast and Slow Pointers (to split) with Two Pointers (to merge) turns a problem that looks like it needs backward traversal into one that only ever needs forward next hops, at O(1) extra space instead of the brute force's O(n) array.
-
Linked Lists — the underlying data structure; both the cut and the reversal are pure
next-pointer rewiring. - Fast and Slow Pointers — stage 1, finding the middle in a single pass without knowing the list's length up front.
- Two Pointers — stage 3, merging the first half and reversed second half by alternating nodes, one from each side per step.
-
Reverse Linked List — stage 2 reuses that exact
prev/curr/nextreversal technique on just the second half.
Reorder List is finding the middle of a train with fast and slow pointers, flipping the back half around, then weaving front and reversed-back together one car at a time.
Walk through why slow ends on the last node of the first half (not the first node of the second half) after the fast/slow loop, for both an odd-length list (1->2->3->4->5) and an even-length list (1->2->3->4). Then explain why the merge loop's stopping condition is second != nil rather than first != nil — what would break if you checked first instead?
⬅️ Previous: Merge Two Sorted Lists · Next: Remove Nth Node From End of List ➡️