Pattern this teaches:Linked List Manipulation
Merge k Sorted Lists
A hard Linked List interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Linked List
- Sheets
- 2
- Core for
- 4 roles
The problem
Merge k sorted linked lists into one sorted linked list.
Example 1
- Input
- [[2,6,8],[3,5,7],[1,4,9]]
- Output
- [1,2,3,4,5,6,7,8,9]
Example 2
- Input
- []
- Output
- []
Example 3
- Input
- [[]]
- Output
- []
Constraints
- 0 <= k <= 10^4
- 0 <= total nodes <= 5*10^4
How to think about it
Updated 2026-09-29The globally smallest unmerged value is always one of the k active heads. Scanning all k lists on every insertion wastes time checking heads that have not changed; organizing candidates into pairwise tournaments or a min-heap isolates the next node in logarithmic time.
Approaches, worst first
Linear repeated merge
time O(k * N) · space O(1)
Merge list 0 with list 1, merge that accumulated result with list 2, and continue sequentially across all k lists. The first list gets repeatedly retraversed up to k times, leading to quadratic node visits proportional to k × N.
Min-heap of active heads
time O(N log k) · space O(k)
Seed a priority queue with the head node of every non-empty list. Repeatedly pop the minimum node, append it to the merged output tail, and push its next successor if present. Maintains heap size at most k throughout the traversal.
Divide and conquer pairwise mergeWrite this one
time O(N log k) · space O(1)
Pair up lists and merge each pair using two-way sorted merge. Repeat on the resulting halved collections in rounds until one list remains. Reaches identical optimal runtime without requiring external priority queue overhead.
Where people lose marks · 3
- Passing empty sublists `[]` directly into the min-heap throws null pointer exceptions if entries are not filtered prior to insertion.
- Merging lists sequentially instead of in balanced pairs degrades the time complexity from O(N log k) to O(k × N), timing out on wide inputs.
- Input where `k == 0` or lists containing exclusively empty elements must cleanly return null rather than attempting to access list references.
The theory behind it
Linked List — the ground this problem stands on. All Linked List problems
What Linked List is
A linked list is a chain of separate cargo cars connected by coupling hooks, scattered anywhere across memory rather than sitting in a tidy contiguous row. Each car, called a node, holds a single piece of data and a pointer directing traffic to the address of the next car in line. Because nodes connect only by directional links, jumping straight to the tenth car is impossible without walking past the first nine.
When to reach for it
Choose a linked list when a problem requires frequent insertions and deletions at known positions without shifting whole blocks of surrounding memory. Problems mentioning pointer splicing, reversing subsequences in place, merging sorted streams, or detecting cycles in linear chains strongly point here. It is ideal when total capacity is unpredictable and memory allocation must happen one individual node at a time.
How the pattern works
Think in terms of pointer rewiring before dereferencing. Keep a dummy head node pointing to the start of the list so modifications to the initial item do not require separate edge logic. Always save references to neighboring nodes into temporary variables before cutting or redirecting forward links. When diagnosing loops or locating middle nodes, advance two references simultaneously at differing velocities so traversal completes without supplementary storage.
More Linked List problems
Target Roles
Core requirement for 4 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .