/23. Merge k Sorted Lists
Previous|Next

23. Merge k Sorted Lists

Hard
Linked Lists59.1% acceptance

Given an array of k singly linked lists, where each linked list is sorted in ascending order, merge all the linked lists into a single sorted linked list and return the head of the merged list. 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: The lists are [2->5], [1->3], [4]. Merged: 1->2->3->4->5.

Example 2

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

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

Explanation: The lists are [-2->0], [-1], [3->4]. Merged: -2->-1->0->3->4.

Example 3

Input: []

Output: None

Explanation: No lists to merge.

Example 4

Input: [None, None]

Output: None

Explanation: All lists are empty.

Constraints

  • 1 <= len(list_heads) <= 104
  • 0 <= length of each linked list <= 500
  • -104 <= node value <= 104
  • Each linked list is sorted in ascending order
  • The total number of nodes across all lists does not exceed 104
Python (current runtime)

Case 1

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

Expected: ListNode(2, ListNode(5, ListNode(7, ListNode(8, ListNode(9)))))

Case 2

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

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

Case 3

Input: [None]

Expected: None

Case 4

Input: [ListNode(1), None, ListNode(2)]

Expected: ListNode(1, ListNode(2))