← all entries
A-044● Day 442026.06.19hardleetcode #23neetcode150

Merge k Sorted Lists

#linked-list#divide-and-conquer#heap-priority-queue#merge-sort
↗ leetcode #23 · merge-k-sorted-lists
01

Problem

· problem
P.044

Merge k Sorted Lists

↗ leetcode #23

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

constraints
  • · 0 ≤ k ≤ 10^4 (number of lists)
  • · 0 ≤ lists[i].length ≤ 500 (per-list node count)
  • · -10^4 ≤ lists[i][j] ≤ 10^4 (node values range)
  • · Each list sorted in ascending order
  • · Total nodes across all lists ≤ 10^4
// paraphrased summary — see source for full text
examples
example 1input → output
[[1,4,5],[1,3,4],[2,6]]
[1,1,2,3,4,4,5,6]
example 2input → output
[]
[]
example 3input → output
[[]]
[]
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Does 'ascending order' mean smallest-to-largest for each linked list?
  • ☐
    What if the input lists array is completely empty (k=0)?
  • ☐
    Can individual lists be empty (e.g., lists = [[]])?
  • ☐
    Can node values be negative?
  • ☐
    What is the maximum total nodes across all lists?
  • ☐
    Can the input lists contain cycles?
  • ☐
    Should output be in descending order?
  • ☐
    Can we modify the original input lists in-place?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Handle empty input
○
if not lists or len(lists) == 0:
○
if len(lists) == 0:
○
if lists:
step 2· Loop until one list remains
○
while len(lists) > 1:
○
while len(lists) > 0:
○
while len(lists) >= 1:
step 3· Iterate by step of 2│ nested
○
for i in range(0, len(lists), 2):
○
for i in range(0, len(lists)):
○
for i in range(len(lists)//2):
step 4· Handle odd count boundary│ │ nested
○
l2 = lists[i + 1] if (i + 1) < len(lists) else None
○
l2 = lists[i + 1]
○
l2 = lists[i + 1] if i + 1 < len(lists) - 1 else None
step 5· Append merged result│ │ nested
○
mergedLists.append(self.mergeList(l1, l2))
○
lists.append(self.mergeList(l1, l2))
○
mergedLists.extend([l1, l2])
step 6· Update for next round│ nested
○
lists = mergedLists
○
mergedLists = lists
○
lists.extend(mergedLists)
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
# Definition for singly-linked list.
2
# class ListNode:
3
#     def __init__(self, val=0, next=None):
4
#         self.val = val
5
#         self.next = next
6
class Solution:
7
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
8
        if not lists or len(lists) == 0:
9
            return None
10
11
        while len(lists) > 1:
12
            mergedLists = []
13
            for i in range(0, len(lists), 2):
14
                l1 = lists[i]
15
                l2 = lists[i + 1] if (i + 1) < len(lists) else None
16
                mergedLists.append(self.mergeList(l1, l2))
17
            lists = mergedLists
18
        return lists[0]
19
20
    def mergeList(self, l1, l2):
21
        dummy = ListNode()
22
        tail = dummy
23
24
        while l1 and l2:
25
            if l1.val < l2.val:
26
                tail.next = l1
27
                l1 = l1.next
28
            else:
29
                tail.next = l2
30
                l2 = l2.next
31
            tail = tail.next
32
        if l1:
33
            tail.next = l1
34
        if l2:
35
            tail.next = l2
36
        return dummy.next
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[[1,4,5],[1,3,4],[2,6]]
→
[1,1,2,3,4,4,5,6]
case 2
[]
→
[]
case 3
[[]]
→
[]
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.