Introduction to the Reorder List Problem
The Reorder List problem is a classic linked list challenge frequently encountered in coding interviews (notably LeetCode 143). Given a singly linked list L0 → L1 → … → Ln-1 → Ln, you must reorder it in-place to 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 rearranged.
While the problem statement sounds simple, it elegantly combines three fundamental linked list techniques: finding the middle, reversing a sublist, and merging two lists. Mastering it sharpens your pointer manipulation skills and prepares you for more complex list-based problems.
Why It Matters
Reorder List is more than an interview exercise. It tests your ability to decompose a complex operation into smaller, reusable primitives — a critical engineering skill. The same building blocks appear in real-world scenarios such as:
- Buffer management: Reorganizing chunks of data streams for round-trip transmission.
- Memory pools: Reordering free blocks for cache-friendly allocation.
- UI rendering: Interleaving head and tail elements for carousel-style layouts.
- Algorithmic foundations: Many divide-and-conquer list algorithms reuse these exact primitives.
Solving it cleanly in Go also demonstrates idiomatic use of pointers, nil checks, and in-place mutation — all hallmarks of efficient systems code.
Understanding the Approach
The Three-Step Strategy
Attempting to reorder the list in a single pass is error-prone. Instead, we split the problem into three well-defined steps:
- Step 1 — Find the middle: Use the slow/fast pointer technique. When the fast pointer reaches the end, the slow pointer sits at (or just before) the midpoint.
- Step 2 — Reverse the second half: Detach the second half from the middle and reverse it in-place.
- Step 3 — Merge alternately: Interleave nodes from the first half and the reversed second half.
This decomposition keeps each function small, testable, and reusable.
Visual Walkthrough
Consider the list 1 → 2 → 3 → 4 → 5:
- After Step 1: first half
1 → 2 → 3, second half4 → 5. - After Step 2: reversed second half
5 → 4. - After Step 3: merged result
1 → 5 → 2 → 4 → 3.
Setting Up the Linked List in Go
First, define the list node type. This mirrors the standard LeetCode definition:
package main
import "fmt"
// ListNode represents a node in a singly linked list.
type ListNode struct {
Val int
Next *ListNode
}
// helper to build a list from a slice
func buildList(vals []int) *ListNode {
if len(vals) == 0 {
return nil
}
head := &ListNode{Val: vals[0]}
cur := head
for i := 1; i < len(vals); i++ {
cur.Next = &ListNode{Val: vals[i]}
cur = cur.Next
}
return head
}
// helper to print a list
func printList(head *ListNode) {
for cur := head; cur != nil; cur = cur.Next {
fmt.Printf("%d", cur.Val)
if cur.Next != nil {
fmt.Print(" -> ")
}
}
fmt.Println()
}
Step 1: Finding the Middle
The slow pointer advances one step at a time, while the fast pointer advances two. When fast can no longer move two steps, slow is at the midpoint. For even-length lists, this lands just before the second half; for odd-length lists, it lands on the true middle node.
// findMiddle returns the node just before the second half begins.
func findMiddle(head *ListNode) *ListNode {
slow, fast := head, head
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
Notice the condition fast.Next != nil && fast.Next.Next != nil. This ensures we stop at the correct boundary regardless of list parity, and it avoids nil dereferences.
Step 2: Reversing the Second Half
Once we have the middle node, we detach the second half and reverse it. The classic iterative reversal uses three pointers: prev, cur, and next.
// reverse reverses the linked list starting at head and returns the new head.
func reverse(head *ListNode) *ListNode {
var prev *ListNode
cur := head
for cur != nil {
next := cur.Next
cur.Next = prev
prev = cur
cur = next
}
return prev
}
This runs in O(n) time and O(1) space. After reversing, the original head of the second half becomes the tail, and the original tail becomes the new head.
Step 3: Merging the Two Halves
Now we interleave nodes from the first half and the reversed second half. We use two pointers and stitch them together one node at a time.
// merge interleaves nodes from l1 and l2 alternately.
func merge(l1, l2 *ListNode) {
for l2 != nil {
next1 := l1.Next
next2 := l2.Next
l1.Next = l2
l2.Next = next1
l1 = next1
l2 = next2
}
}
The loop terminates when l2 is exhausted. Because of how we split the list, the first half is always at least as long as the second, so we never need to handle leftover nodes in l1.
Putting It All Together
Now combine the three steps into the main reorderList function:
// reorderList reorders the list in-place as L0 -> Ln -> L1 -> Ln-1 -> ...
func reorderList(head *ListNode) {
if head == nil || head.Next == nil {
return
}
// Step 1: find the middle
mid := findMiddle(head)
// Step 2: detach and reverse the second half
secondHalf := mid.Next
mid.Next = nil
secondHalf = reverse(secondHalf)
// Step 3: merge the two halves
merge(head, secondHalf)
}
Complete Runnable Example
Here is the full program you can copy, paste, and run:
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func buildList(vals []int) *ListNode {
if len(vals) == 0 {
return nil
}
head := &ListNode{Val: vals[0]}
cur := head
for i := 1; i < len(vals); i++ {
cur.Next = &ListNode{Val: vals[i]}
cur = cur.Next
}
return head
}
func printList(head *ListNode) {
for cur := head; cur != nil; cur = cur.Next {
fmt.Printf("%d", cur.Val)
if cur.Next != nil {
fmt.Print(" -> ")
}
}
fmt.Println()
}
func findMiddle(head *ListNode) *ListNode {
slow, fast := head, head
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
func reverse(head *ListNode) *ListNode {
var prev *ListNode
cur := head
for cur != nil {
next := cur.Next
cur.Next = prev
prev = cur
cur = next
}
return prev
}
func merge(l1, l2 *ListNode) {
for l2 != nil {
next1 := l1.Next
next2 := l2.Next
l1.Next = l2
l2.Next = next1
l1 = next1
l2 = next2
}
}
func reorderList(head *ListNode) {
if head == nil || head.Next == nil {
return
}
mid := findMiddle(head)
secondHalf := mid.Next
mid.Next = nil
secondHalf = reverse(secondHalf)
merge(head, secondHalf)
}
func main() {
// Odd-length list
l1 := buildList([]int{1, 2, 3, 4, 5})
fmt.Print("Before: ")
printList(l1)
reorderList(l1)
fmt.Print("After: ")
printList(l1)
// Even-length list
l2 := buildList([]int{1, 2, 3, 4})
fmt.Print("Before: ")
printList(l2)
reorderList(l2)
fmt.Print("After: ")
printList(l2)
}
Expected output:
Before: 1 -> 2 -> 3 -> 4 -> 5
After: 1 -> 5 -> 2 -> 4 -> 3
Before: 1 -> 2 -> 3 -> 4
After: 1 -> 4 -> 2 -> 3
Complexity Analysis
- Time complexity: O(n). Each of the three steps traverses the list a constant number of times.
- Space complexity: O(1). All operations are performed in-place using a fixed number of pointers.
This is optimal — you cannot do better than linear time since every node must be visited, and the in-place requirement forbids auxiliary data structures.
Best Practices
Guard Against Edge Cases Early
Always handle empty lists and single-node lists at the top of reorderList. Failing to do so leads to nil pointer dereferences in findMiddle or reverse.
Keep Functions Single-Purpose
Resist the temptation to inline everything into one giant function. Separate findMiddle, reverse, and merge are easier to test, debug, and reuse in other problems such as "Palindrome Linked List" or "Reverse Linked List II".
Detach Before Reversing
Setting mid.Next = nil before reversing the second half is essential. Without it, the first half still points into the reversed segment, creating cycles that produce infinite loops during merging or printing.
Use Clear Pointer Naming
Names like next1, next2, prev, and cur make the intent obvious. Avoid cryptic single-letter variables in pointer-heavy code — readability matters more than brevity here.
Test Both Parities
Always test with both odd- and even-length lists. The middle-finding logic behaves slightly differently for each, and bugs often hide in the boundary between the two halves.
Avoid Recursive Reversal on Long Lists
While a recursive reverse is elegant, it consumes O(n) stack space and risks stack overflow on very long lists. The iterative version is safer and equally readable.
Common Pitfalls
- Forgetting to detach: Omitting
mid.Next = nilcauses cycles in the merged list. - Wrong loop condition in findMiddle: Using
fast != nil && fast.Next != nilshifts the midpoint by one, breaking even-length lists. - Merging until l1 is nil: The loop should be driven by
l2, notl1, because the first half may be one node longer. - Modifying node values: The problem forbids changing
Val; onlyNextpointers may be rewired.
Conclusion
Solving Reorder List in Go is a rewarding exercise that distills three essential linked list techniques into a single, cohesive solution. By decomposing the problem into finding the middle, reversing the second half, and merging alternately, you produce code that is both efficient and easy to reason about. The O(n) time and O(1) space solution is optimal, and the modular design means each helper function can be reused across a family of related problems. With the patterns and best practices covered here, you are well-equipped to tackle not only this problem but any pointer-manipulation challenge that comes your way in Go.