/23. Merge k Sorted Lists

23. Merge k Sorted Lists

Hard

Linked Lists59.1% acceptance

Given an array of k singly-linked lists, each sorted in ascending order, merge all the lists into a single sorted singly-linked list. Return the head node of the merged list. Each input list is represented by its head node. If the input array is empty or contains only empty lists, return None.

Example 1

Input: [ListNode(2, ListNode(5)), ListNode(1, ListNode(3)), ListNode(4)]

Output: ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))

Explanation: Merging [2->5], [1->3], [4] yields [1->2->3->4->5].

Example 2

Input: [ListNode(-3, ListNode(0)), ListNode(-2, ListNode(1, ListNode(2)))]

Output: ListNode(-3, ListNode(-2, ListNode(0, ListNode(1, ListNode(2)))))

Explanation: Merging [-3->0], [-2->1->2] yields [-3->-2->0->1->2].

Example 3

Input: []

Output: None

Explanation: Empty input yields empty output.

Example 4

Input: [None, None]

Output: None

Explanation: All lists are empty.

Constraints

1 <= len(list_heads) <= 10⁴
0 <= length of each linked list <= 500
-10⁴ <= node value <= 10⁴
Each linked list is sorted in ascending order
Total number of nodes across all lists <= 10⁴

Python (current runtime)

Case 1

Input: [ListNode(7, ListNode(8)), ListNode(1, ListNode(9)), ListNode(5, ListNode(6))]

Expected: ListNode(1, ListNode(5, ListNode(6, ListNode(7, ListNode(8, ListNode(9))))))

Case 2

Input: [ListNode(0), ListNode(-1, ListNode(2)), ListNode(3)]

Expected: ListNode(-1, ListNode(0, ListNode(2, ListNode(3))))

Case 3

Input: [None]

Expected: None

Case 4

Input: [ListNode(4, ListNode(10)), None, ListNode(5)]

Expected: ListNode(4, ListNode(5, ListNode(10)))