---
###### tags: `Leetcode`
---
# Leetcode 23. Merge k Sorted Lists

[link](https://leetcode.com/problems/merge-k-sorted-lists/)

---

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.

#### Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  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 3:

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 will not exceed 104.

---

The given code provides a solution to the problem of merging k sorted linked lists into a single sorted linked list. The mergeKLists function takes a list of linked lists (lists) as input and returns the merged list.

The function first checks if the input list is empty or None, in which case it returns None. Otherwise, it continues with the merging process.

The function uses a while loop that runs as long as there are more than one list remaining in the lists list. Inside the loop, it creates an empty list called mergedLists, which will store the merged results of pairs of linked lists.

Then, it iterates over the lists list with a step size of 2. For each pair of linked lists, it calls the mergeList function and appends the merged list to mergedLists. If the number of lists is odd, the last list is merged with None.

After processing all the pairs, the lists variable is updated with the mergedLists list, and the loop continues until there is only one list remaining.

Finally, the function returns the first (and only) element in the lists list, which represents the merged result.

The mergeList function is a helper function that merges two sorted linked lists (l1 and l2) into a single sorted list. It uses a dummy node and a tail pointer to construct the merged list. The function iterates over both lists, comparing the values at each node and appending the smaller value to the merged list. It continues this process until one of the lists reaches the end. Then, it appends the remaining nodes from the non-empty list to the merged list.

Overall, the code efficiently merges the given linked lists by dividing them into pairs and merging each pair until a single merged list is obtained.

#### Solution 1

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists or len(lists) == 0:
            return None
            
        while len(lists) > 1:
            mergedLists = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if (i + 1) < len(lists) else None
                mergedLists.append(self.mergeList(l1, l2))
            
            lists = mergedLists

        return lists[0]


    def mergeList(self, l1, l2):
        dummy = ListNode()
        tail = dummy
        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            
            tail = tail.next

        if l1:
            tail.next = l1
        
        if l2:
            tail.next = l2
            
        return dummy.next
        

O(T): O(Nlogk)
O(S): O(k)