Dev Skills
Go·Go for coding rounds

Merge two sorted lists

A dummy head node removes every special case, and the leftover tail is attached in one line.

Topic 32 of 98 · 5 min to read · 45 min to build
After this topic you can
  • Write a merge of two sorted lists using a dummy head.
  • Explain why <= keeps the merge stable.
  • Predict the result when one list is nil.

The problem

Given two sorted linked lists, merge them into one sorted list by relinking their nodes.

Brute force first

Copy every value from both lists into one slice, slices.Sort it, and build a brand-new list from the result.

O((n+m) log(n+m)) time, O(n+m) space. It ignores that the inputs are already sorted, which is the whole hint.

The approach

Keep a tail pointer. Compare the two heads, attach the smaller one, step that list forward. When one list runs out, attach the rest of the other in one go. O(n + m) time, O(1) extra space.

merge_lists.go
package main
import "fmt"
type Node struct {
	Val  int
	Next *Node
}
// merge joins two sorted lists into one sorted list, reusing their nodes.
// The dummy head means there is no special case for the first node.
func merge(a, b *Node) *Node {
	var dummy Node
	tail := &dummy
	for a != nil && b != nil {
		if a.Val <= b.Val { // <= keeps equal values in their original order
			tail.Next, a = a, a.Next
		} else {
			tail.Next, b = b, b.Next
		}
		tail = tail.Next
	}
	if a != nil {
		tail.Next = a // one list ran out: attach the rest of the other
	} else {
		tail.Next = b
	}
	return dummy.Next
}
func build(vals ...int) *Node {
	var head *Node
	for i := len(vals) - 1; i >= 0; i-- {
		head = &Node{Val: vals[i], Next: head}
	}
	return head
}
func show(n *Node) {
	for ; n != nil; n = n.Next {
		fmt.Print(n.Val, " ")
	}
	fmt.Println()
}
func main() {
	show(merge(build(1, 3, 5), build(2, 4, 6, 8))) // 1 2 3 4 5 6 8
	show(merge(nil, build(1, 2)))                  // 1 2
}

Dry run

a = 1 → 3 → 5, b = 2 → 4:

compareattachresult so far
1 vs 21 (from a)1
3 vs 22 (from b)1 2
3 vs 43 (from a)1 2 3
5 vs 44 (from b)1 2 3 4
b is emptyrest of a (5)1 2 3 4 5

Go-specific gotchas

  • A dummy node on the stack (var dummy Node) means the first node is not a special case. Return dummy.Next.
  • `<=` rather than `<` keeps equal values in their original order. That is called a stable merge.
  • Do not copy nodes unless asked. Relinking is the point, and it avoids allocating.
  • The same merge step is the heart of merge sort. Say so; it shows you see the connection.
The short version
  • Dummy head, tail pointer, compare and attach.
  • Attach the leftover list in one assignment.
  • O(n + m) time, no new nodes.
Remember: When the first item of a result is a special case, add a dummy in front of it.
Build this before moving on
Merge k sorted lists. First do it pairwise, then with a min-heap from container/heap, and compare the complexity.
Coding challenge · checked by tests
Write mergeLists(a, b *Node) *Node that merges two sorted linked lists into one sorted list by splicing the existing nodes (no new nodes) and returns its head. Equal values may come in either order. Example: 1 → 3 → 5 and 2 → 4 → 1 → 2 → 3 → 4 → 5.

Tab indents. Press Esc, then Tab, to leave the editor.

Then try these in your own editor
  1. 1The main task: Merge k sorted lists. First do it pairwise, then with a min-heap from container/heap, and compare the complexity.
  2. 2Dry run the merge with a = nil and b = 1 → 2. Does the loop run at all?
  3. 3Merge two sorted slices []int into a new sorted slice in O(n + m).
Official documentation
Check yourselfTake the Go for coding rounds test