# 23 Merge k Sorted Lists

You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order.

Example 1:

``````Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
``````

Example 2:

``````Input: lists = []
Output: []
``````

Example 2:

``````Input: lists = [[]]
Output: []
``````

Constraints:

• `k == lists.length`
• `0 <= k <= 104`
• `0 <= lists[i].length <= 500`
• `-104 <= lists[i][j] <= 104`
• `lists[i]` is sorted in ascending order.
• The sum of `lists[i].length` won't exceed `104`.
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 `````` ``````# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: n = len(lists) if n == 0: return None elif n == 1: return lists[0] else: left = self.mergeKLists(lists[:n//2]) right = self.mergeKLists(lists[n//2:]) return self.merge2Lists(left, right) def merge2Lists(self, l1, l2): head = point = ListNode(0) while l1 and l2: if l1.val <= l2.val: point.next = l1 l1 = l1.next else: point.next = l2 l2 = l1 l1 = point.next.next point = point.next if not l1: point.next=l2 else: point.next=l1 return head.next``````