DSA sheet · Linked List · Merge & sort pattern (last problem)

Merge K Sorted Lists

This is the last problem of the merge & sort pattern, and it's a famous hard interview question. It builds directly on Merge Two Sorted Lists: instead of two sorted lists, we get k of them and must merge them all into one sorted list. The teacher spreads four approaches over two videos. Video 1: (A) dump every value in an array and sort it, (B) merge the lists one by one, (C) a min-heap (priority queue) that always hands us the smallest front node. Video 2: (D) divide and conquer, exactly like merge sort, but the "elements" are whole lists. The key lesson: C and D both bring the cost down to N log k, by never comparing more than they need to.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you need first (node, walking, dummy + tail, merging two lists, heaps, merge sort)
• Part A · Brute force: collect all values, sort, rebuild
• Part B · Merge the lists one by one
• Part C · Min-heap (priority queue) of the k front nodes
• Part D · Divide and conquer (video 2)
• Part E · Revision page

Part 0 · Before starting

What is a linked list node?

A linked list is a chain of nodes. Each node has a value (val) and a link to the next node (next). The first node is the head. The last node points to None. In this problem we receive a Python list lists of k heads, and each head may be None (an empty list).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

lists[0]:  [1] → [4] → [5] → None
lists[1]:  [1] → [3] → [4] → None
lists[2]:  [2] → [6] → None

Walking, and no index access

We move along a list with curr = curr.next until curr is None. There is no list[i]. Reaching position i costs i steps (O(n)), so we only ever read the front of each list and move forward.

Save next before you change a pointer

When we take a node out of its list and attach it to our answer, we write tail.next = node. The node's own next is still the road to the rest of its old list. So we move that list's pointer forward (l1 = l1.next), or push node.next into the heap, before that link is ever overwritten. If we lose it, the rest of that list is gone.

Dummy node + tail pointer (merging with a tail)

The answer list is built one node at a time. A fake dummy = ListNode(0) sits in front, and tail always stands on the last node. To add: tail.next = node, then tail = tail.next. The answer is dummy.next. The dummy means the "first node" never needs a special case.

Merge Two Sorted Lists (the prerequisite)

The teacher quickly recaps it with 1 → 4 → 5 and 1 → 3 → 4. Put l1 and l2 on the two heads. Each time, attach the smaller front node to the tail and move that list forward (on a tie, take l1). When one list runs out, the other one is already sorted, so we don't walk through it: just hang the whole remaining part on the tail with one link.

def merge_two(l1, l2):
    dummy = ListNode(0)
    tail = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1        # take l1's front node
            l1 = l1.next          # move l1 BEFORE that link is ever changed
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 if l1 else l2  # the leftover part is already sorted
    return dummy.next

l1: [1] → [4] → [5]         l2: [1] → [3] → [4]
take 1(l1), 1(l2), 3, 4(l1), 4(l2) → l2 is empty → hang [5] on the tail
result: [1] → [1] → [3] → [4] → [4] → [5] → None

Cost: one step per node, so O(len1 + len2).

A heap (priority queue)

A min-heap is a box that always gives you its smallest item first. Adding an item (push) and removing the smallest (pop) each cost O(log size), much cheaper than scanning everything. Inside, it is stored as a tree-shaped array where every parent is ≤ its children, so the smallest is always at the top. In Python we use heapq on a normal list: heapq.heappush(h, x), heapq.heappop(h). Python's heapq is already a min-heap.

heap array [1, 1, 2, 2]  as a tree:
        1
       / \
      1   2          every parent ≤ its children
     /                → the top (1) is the minimum
    2

Merge sort in one picture (for Part D)

The teacher recalls merge sort with [2, 5, 4, 3]: keep splitting in half until each piece has one element (a single element is always sorted), then merge the pieces back up in pairs.

          [2 5 4 3]
          /        \
      [2 5]        [4 3]          split
      /   \        /   \
    [2]   [5]    [4]   [3]        size 1 → sorted
      \   /        \   /
      [2 5]        [3 4]          merge pairs
          \        /
          [2 3 4 5]               merge again

Part A · Brute force: collect, sort, rebuild

LeetCode 23 · Merge k Sorted Lists

1The question in simple words

You get an array of k linked lists. Each list is already sorted in increasing order. Merge all of them into one sorted linked list and return its head.

input:  [1 → 4 → 5,  1 → 3 → 4,  2 → 6]
output:  1 → 1 → 2 → 3 → 4 → 4 → 5 → 6

input:  []        → output: None   (no lists at all)
input:  [None]    → output: None   (one empty list)

2What the constraints tell us

• k (the number of lists) goes from 0 to 10⁴, and each list has 0 to 500 nodes. Zero is allowed for both, so we need base cases: no lists at all, or lists that are empty.
• The teacher multiplies: up to 10⁴ × 500 = 5 × 10⁶ nodes in total. That's below the ~10⁸ danger line, so even a slower solution passes here. It will be slow, but it won't TLE. (LeetCode also caps the total at 10⁴ nodes, which makes it even safer.)
• She also asks: what if k were 10⁶ and each list 10³ long? That's 10⁹ nodes, and the brute force would TLE. The constraints decide whether brute force is enough.

Notation for this page: k = number of lists, n = length of one list, N = total nodes (about k·n). The teacher writes "kn" for the total.

3Intuition

Forget that each list is sorted. Pour every value into one bucket, sort the bucket, and build a new list from it. This works even if you've never seen the merge algorithm.

4Building the logic

• Outer loop: for every head in lists. Inner loop: walk that list with head = head.next, appending each head.val to nums. For the example, nums = [1, 4, 5, 1, 3, 4, 2, 6].
• The lists were sorted on their own, but nums as a whole is not → nums.sort() → [1, 1, 2, 3, 4, 4, 5, 6].
• Build a new linked list with a dummy node, one ListNode(v) per value, and return dummy.next.

5Approach steps

1. Walk every list and collect all values into nums.
2. Sort nums.
3. Build a new list from nums with a dummy and a tail. Return dummy.next.

6Code (Python)

class Solution:
    def mergeKLists(self, lists):
        nums = []
        for head in lists:               # k lists
            while head:                  # n nodes each
                nums.append(head.val)
                head = head.next
        nums.sort()                      # N log N

        dummy = ListNode(0)
        curr = dummy
        for v in nums:                   # build a fresh list
            curr.next = ListNode(v)
            curr = curr.next
        return dummy.next

7Code line by line

8Dry run

9Complexity & remember

• Time O(N log N): collecting is O(N) (the teacher writes O(k·n)), sorting an array of length L costs L log L, and here L = N = k·n. With N = 5×10⁶ it's slow, but it passes.
• Space O(N): the nums array is extra (the returned list we can't avoid).

Part B · Merge the lists one by one

1The question

Same question. Now we use the fact that each list is sorted: two sorted lists can be merged in linear time, with no sort at all.

2What the constraints tell us

• lists can be empty → base case: if not lists: return None. (Empty lists inside it are fine, because merge_two handles None.)
• With the given limits this approach is accepted (the teacher submits it), but it's still not the best.

3Intuition: a snowball

Merge list 0 and list 1 into one sorted list. Merge that result with list 2. Merge that result with list 3… Like a snowball rolling forward, the result keeps growing and swallows one more list each time.

L0 + L1 → R1
R1 + L2 → R2
R2 + L3 → R3   = answer

4Building the logic

• Start with result = lists[0]. We know there's at least one list, because of the base case.
• For i from 1 to k−1: result = merge_two(result, lists[i]).
• Return result.

5Approach steps

1. If there are no lists, return None.
2. result = lists[0].
3. For each next list: result = merge_two(result, that list).
4. Return result.

6Code (Python)

class Solution:
    def mergeTwo(self, l1, l2):
        dummy = ListNode(0)
        tail = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        tail.next = l1 if l1 else l2
        return dummy.next

    def mergeKLists(self, lists):
        if not lists:                    # k = 0
            return None
        result = lists[0]
        for i in range(1, len(lists)):
            result = self.mergeTwo(result, lists[i])   # snowball
        return result

7Code line by line

8Dry run (the 4-list example from the videos)

L0: 1 → 4 → 5     L1: 1 → 3 → 4     L2: 2 → 6     L3: 2 → 5 → 7

Notice how the early nodes (the 1s) get walked over in every merge. That repeated work is what makes this O(k·N).

9Complexity & remember

• Time O(k·N) (about k²·n): see the correction above.
• Space O(1) extra with the relinking merge.

Part C · Min-heap of the k front nodes

1The question

Same question. Goal: pick each next node of the answer cheaply.

2What the constraints tell us

k can be up to 10⁴. Scanning all k fronts for every node would cost N·k. A heap finds the minimum of k items in log k instead.

3Intuition: only the fronts matter

The very first node of the answer must be the smallest value overall. Since each list is sorted, the smallest value of each list is its first node. So the overall smallest is the smallest of the k front nodes. We never need to look deeper.

Picture k queues at a ticket counter, each queue already lined up by height. To call the shortest person, you only compare the people at the front of each queue. When you call someone, the next person in that queue steps up to the front.

To find "the smallest of k fronts" quickly, again and again, we keep the fronts in a min-heap. Each pop gives the smallest in O(log k), instead of comparing all k.

4Building the logic

• Start: push the head of every non-empty list. For the 4-list example the heap holds 1, 1, 2, 2. We store the nodes (not just numbers), so we can link them directly and follow .next.
• Repeat until the heap is empty: pop the smallest node, attach it to the tail, move the tail.
• Refill: the popped node's list now has a new front, node.next. If it exists, push it. This is the same as "move l1 forward" in Merge Two.
• Return dummy.next.

5Approach steps

1. Push (head.val, i, head) for every non-empty list.
2. dummy = ListNode(0), tail = dummy.
3. While the heap is not empty: pop the smallest node, tail.next = node, tail = node; if node.next, push it.
4. Return dummy.next.

6Code (Python)

import heapq

class Solution:
    def mergeKLists(self, lists):
        heap = []
        for i, head in enumerate(lists):
            if head:                                  # skip empty lists
                heapq.heappush(heap, (head.val, i, head))

        dummy = ListNode(0)
        tail = dummy
        while heap:
            val, i, node = heapq.heappop(heap)        # smallest front node
            tail.next = node
            tail = node
            if node.next:                             # its list's new front
                heapq.heappush(heap, (node.next.val, i, node.next))
        return dummy.next

7Code line by line

8Dry run: the heap step by step

L0: 1 → 4 → 5     L1: 1 → 3 → 4     L2: 2 → 6     L3: 2 → 5 → 7

Heap items are written value(list). I show the heap contents in sorted order to make them easy to read. Inside, it's a tree, but the item popped is always the first one shown. Yellow = the item popped at that step.

Answer list, built one attach at a time:

dummy → [1] → [1] → [2] → [2] → [3] → [4] → [4] → [5] → [5] → [6] → [7] → None
                                                                        ↑
                                                                      tail

Snapshot of the heap as a tree, after step 4 (items 3(L1), 4(L0), 5(L3), 6(L2)):

         3
        / \
       4   5        the smallest (3) sits at the top,
      /             so the next pop is O(log k)
     6

The heap never holds more than k = 4 items, one per list that still has nodes. That's where the "log k" comes from.

The teacher also runs the 3-list example (1→4→5, 1→3→4, 2→6): heap 1,1,2 → pop 1, push 4 → 1,2,4 → pop 1, push 3 → 2,3,4 → pop 2, push 6 → 3,4,6 → pop 3, push 4 → 4,4,6 → pop 4, push 5 → 4,5,6 → pop 4 → 5,6 → pop 5 → 6 → pop 6 → empty. Answer 1 1 2 3 4 4 5 6.

9Complexity & remember

• Time O(N log k): every one of the N nodes is pushed once and popped once, and each heap operation costs O(log k), because the heap holds at most k items. Compare: N log N for Part A, and k·N for Part B.
• Space O(k): the heap. We relink the original nodes, so no other extra space.

Part D · Divide and conquer (video 2)

1The question

Same question, solved the merge-sort way: the "elements" are whole lists, and "merge" is Merge Two Sorted Lists.

2What the constraints tell us

• lists may be empty (or None) → return None before dividing.
• A list inside may be empty → merge_two already handles None.
• k up to 10⁴ → the recursion depth is only about log₂ k ≈ 14, no problem.

3Intuition: a knockout tournament

In merge sort, an array of length 1 is already sorted. Here, one linked list is already sorted (the question promises it). So, exactly like merge sort: split the k lists into a left half and a right half, solve each half (recursively) into one sorted list, then merge the two halves with Merge Two.

It's like a knockout tournament: lists are paired up and merged in round 1, the winners are paired up in round 2, and so on until one list is left. Unlike the snowball in Part B, every round merges lists of similar size, so no node gets re-walked again and again.

The teacher's point: 1 → 4 → 5 and 1 → 3 → 4 are each sorted, but together they aren't. If they had been 1 → 4 → 5 and 6 → 7 → 8, simply joining them would have worked. Since we can't count on that, we have to merge.

4Building the logic

Divide by index, not by copying

We don't slice the array. A function divide(lists, left, right) works on the index range left..right. The first call is divide(lists, 0, k-1).

• mid = left + (right - left) // 2. The teacher mentions both (left + right) // 2 and this form, and refers back to binary search: the second form avoids integer overflow in Java/C++. In Python both are fine. For 0..3: mid = 1 (1.5 rounded down). For 0..1: mid = 0.
• Left half = left..mid, right half = mid+1..right.

Base case: one list → it's already sorted

When left == right, the range holds exactly one list. Don't divide further: just return lists[left].

Conquer: merge what comes back

l1 = divide(left, mid) returns one sorted list for the left half, and l2 = divide(mid+1, right) one for the right half. Two sorted lists → return merge_two(l1, l2). That returned list becomes the l1 or l2 of the caller one level up.

5Approach steps

1. If lists is empty → return None.
2. Return divide(0, k-1).
3. In divide(l, r): if l == r return lists[l].
4. mid = l + (r − l) // 2; left = divide(l, mid); right = divide(mid+1, r).
5. Return merge_two(left, right).

6Code (Python)

class Solution:
    def mergeTwo(self, l1, l2):
        dummy = ListNode(0)
        tail = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        tail.next = l1 if l1 else l2
        return dummy.next

    def divide(self, lists, left, right):
        if left == right:                        # one list: already sorted
            return lists[left]
        mid = left + (right - left) // 2
        l1 = self.divide(lists, left, mid)       # sorted left half
        l2 = self.divide(lists, mid + 1, right)  # sorted right half
        return self.mergeTwo(l1, l2)             # conquer

    def mergeKLists(self, lists):
        if not lists:                            # no lists at all
            return None
        return self.divide(lists, 0, len(lists) - 1)

7Code line by line

8Dry run: the pairing tree

                       divide(0, 3)   mid = 1
                     /                           \
          divide(0, 1)  mid = 0             divide(2, 3)  mid = 2
          /            \                    /            \
   divide(0,0)     divide(1,1)       divide(2,2)     divide(3,3)
   1 → 4 → 5       1 → 3 → 4         2 → 6           2 → 5 → 7
          \            /                    \            /
     merge → 1 1 3 4 4 5                merge → 2 2 5 6 7
                     \                           /
               merge → 1 1 2 2 3 4 4 5 5 6 7     ← final answer

1. divide(0,3): mid = 1 → first solve the left half 0..1. (0,3) waits.
2. divide(0,1): mid = 0 → left half 0..0.
3. divide(0,0): one list → return 1 → 4 → 5.
4. Back in (0,1): right half divide(1,1) → return 1 → 3 → 4.
5. (0,1) merges them → 1 1 3 4 4 5, returned to (0,3) as its l1.
6. (0,3) now solves the right half: divide(2,3), mid = 2 → divide(2,2) returns 2 → 6, divide(3,3) returns 2 → 5 → 7 → merge → 2 2 5 6 7. This is (0,3)'s l2.
7. (0,3) merges l1 and l2 → 1 1 2 2 3 4 4 5 5 6 7. The stack is empty. Done ✓

The newest call is on top (red). Each call returns one sorted list to the call below it.

Why it's N log k: count nodes per level

The teacher counts the nodes at each level of the tree. There are 11 nodes in total, and every level merges all 11 once (bottom level: 6 + 5 nodes across the two merges; top level: 11 nodes). The number of levels is how many times you can halve k: log₂ 4 = 2.

9Complexity & remember

• Time O(N log k): log k levels, and each level walks all N nodes once. That's the same as the heap.
• Space: the recursion stack is O(log k). The teacher notes the merge can either create new nodes (O(N) extra) or relink the existing ones (O(1) extra, as on this page). So the extra space is "linear or constant, depending on the merge".

Part E · Revision page

N = total nodes, k = number of lists. The teacher writes the total as "kn", so her "n log k" for C and D means the same as N log k here.

def build(vals):
    dummy = ListNode(0)
    t = dummy
    for v in vals:
        t.next = ListNode(v)
        t = t.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

s = Solution()
lists = [build([1, 4, 5]), build([1, 3, 4]), build([2, 6]), build([2, 5, 7])]
print(to_list(s.mergeKLists(lists)))        # [1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 7]
print(to_list(s.mergeKLists([])))           # []
print(to_list(s.mergeKLists([None])))       # []

Based on these videos: Merge K Sorted Lists · Part 1 (brute force, one by one, priority queue) · Merge K Sorted Lists · Part 2 (divide and conquer)