Workspace

Problem workspace

3 day streakD

Merge k Sorted Lists

HardLinked ListsMerging & sorting

The challenge

Merge k sorted lists into a single sorted chain, reusing their nodes.

Inputs are sorted, acyclic, and pairwise disjoint. N is their total node count.

Example

[1, 4], [2, 5], [3, 6] → [1, 2, 3, 4, 5, 6].

Use the walkthrough below to inspect the input and each state change.

See Merge k lists, step by step

Follow the pointers. Watch each link change.

6 nodes · singly linkedIDs = node identity · ∅ = null
Three sorted lists: Read the inputIDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links. Node positions stay fixed while arrows change. The pointer strip and node table below give the same state in text.head · headA1A14A2∅headB2B15B2∅headC3C16C2∅
CurrentResultYellow arrow: changed next link
headA1headAA1headBB1headCC1
Inspect node links
Each row is a distinct node object. D is the dummy sentinel.
NodeValueNext
A11A2
A24null
B12B2
B25null
C13C2
C26null
Step 01 / 9

Read the input

IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.

Start from the input head pointers.
View original input

A: 1 (A1) → 4 (A2); B: 2 (B1) → 5 (B2); C: 3 (C1) → 6 (C2); parameters: {}

Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.

Put it into code

The smallest available front is always the next output node.

Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.

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


import heapq
from itertools import count


def merge_k(lists):
    heap, serial = [], count()
    for head in lists:
        if head:
            heapq.heappush(heap, (head.val, next(serial), head))
    dummy = Node()
    tail = dummy
    while heap:
        _, _, node = heapq.heappop(heap)
        nxt = node.next
        tail.next = node
        tail = node
        if nxt:
            heapq.heappush(heap, (nxt.val, next(serial), nxt))
    tail.next = None
    return dummy.next

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap