Skip to content

Merging the Sorted Logs

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 12 Session 1 (Click for link to problem statements)

Merging the Sorted Logs

A distributed system produced k server logs, each already sorted by timestamp and given as the head of a linked list. lists holds those heads.

Merge all of them into a single sorted linked list and return its head.

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

def merge_k_lists(lists):
    pass

Problem Highlights

  • 💡 Difficulty: Hard
  • ⏰ Time to complete: 30-40 mins
  • 🛠️ Topics: Linked Lists, Heaps (Priority Queues), K-way Merge

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • Q: What exactly does lists contain?

    • A: A list of k linked list heads. Each linked list is already sorted in ascending order, but the lists are independent of one another.

  • Q: Can lists be empty, or contain empty (None) lists?

    • A: Yes. If lists is empty, or every entry is None, the merged result is an empty list, so the function should return None.

  • Q: Do we need to create new nodes for the merged list?

    • A: No. We can reuse the existing nodes and simply rewire their next pointers, which keeps the space overhead low.
HAPPY CASE
Input: lists = [1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6]
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
Explanation: All three sorted logs are interleaved into one sorted list. Printing the result gives "1 1 2 3 4 4 5 6".

EDGE CASE
Input: lists = []
Output: None
Explanation: There are no logs to merge, so the merged list is empty.

Input: lists = [None, 0 -> 5, None]
Output: 0 -> 5
Explanation: Empty logs contribute nothing; the merged result is just the one non-empty log.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For K-way Merge Problems, we can consider the following approaches:

  • Min-Heap (Priority Queue): Keep the current front node of every list in a heap so we can grab the overall smallest value in O(log k) time. This is the classic pattern whenever we merge k sorted sequences.
  • Divide and Conquer: Repeatedly merge pairs of lists (like merge sort's merge step) until one list remains. Same time complexity as the heap approach.
  • Brute Force: Merge lists one by one into an accumulator, or collect every value into an array and sort it. Simpler but slower or more space-hungry.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: At any moment, the next node of the merged list must be the smallest node among the current heads of the k lists. Push each list's head into a min-heap, then repeatedly pop the smallest node, append it to the merged list, and push that node's successor into the heap. Because ListNode objects can't be compared directly, store (value, list_index, node) tuples so ties on value are broken by the index.

1) Create an empty min-heap.
2) For each list head in `lists` (with its index i):
   a) If the head is not None, push (head.val, i, head) onto the heap.
3) Create a dummy node and a `tail` pointer starting at the dummy.
4) While the heap is not empty:
   a) Pop the smallest tuple (val, i, node) from the heap.
   b) Attach `node` after `tail` and advance `tail`.
   c) If `node.next` exists, push (node.next.val, i, node.next) onto the heap.
5) Return dummy.next as the head of the merged list.

⚠️ Common Mistakes

  • Pushing bare ListNode objects onto the heap — Python raises a TypeError when two nodes with equal values get compared. Include a tie-breaker (the list index) in the tuple.
  • Forgetting to skip None heads when seeding the heap, which crashes on empty lists.
  • Forgetting to push the popped node's next back onto the heap, which drops the rest of that log.
  • Returning the dummy node itself instead of dummy.next.

4: I-mplement

Implement the code to solve the algorithm.

import heapq

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

def merge_k_lists(lists):
    heap = []
    # Seed the heap with the head of each non-empty list.
    # The index i breaks ties so nodes never get compared directly.
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(heap, (head.val, i, head))

    dummy = ListNode()
    tail = dummy
    while heap:
        # The smallest remaining node across all lists
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        # Replace it with its successor from the same list
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: lists = [1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6]

    • Seed the heap: [(1, 0), (1, 1), (2, 2)] — the heads of all three logs.
    • Pop 1 (list 0), push 4; pop 1 (list 1), push 3; pop 2 (list 2), push 6.
    • Pop 3 (list 1), push 4; pop 4 (list 0), push 5; pop 4 (list 1), list exhausted.
    • Pop 5 (list 0), then pop 6 (list 2); the heap is empty.
    • Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6, printed as "1 1 2 3 4 4 5 6".

  • Input: lists = []

    • The heap is never seeded, the while loop never runs.
    • Output: None

  • Input: lists = [None, 0 -> 5, None]

    • Only the middle head is pushed; the merged list is that log unchanged.
    • Output: 0 -> 5

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the total number of nodes across all lists and k is the number of lists.

  • Time Complexity: O(N log k) because each of the N nodes is pushed onto and popped from a heap that holds at most k entries, and each heap operation costs O(log k).
  • Space Complexity: O(k) for the heap. The merged list reuses the existing nodes, so no additional per-node storage is needed.

Clone this wiki locally