> For the complete documentation index, see [llms.txt](https://yyloumike.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yyloumike.gitbook.io/leetcode/linked-list/0023.-merge-k-sorted-lists.md).

# 0023. Merge k Sorted Lists

Hard  |  Linked List + Sort  |  76 ms (98.81%),  22.3 MB (39.22%)

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0023-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***.*
{% endtab %}

{% tab title=" ✍🏻 Constraints & Example" %}
**Constraints:**

* `k == lists.length`
* `0 <= k <= 10^4`
* `0 <= lists[i].length <= 500`
* `-10^4 <= lists[i][j] <= 10^4`
* `lists[i]` is sorted in **ascending order**.
* The sum of `lists[i].length` won't exceed `10^4`.

```
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

Input: lists = []
Output: []

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

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
**Extended question from LeetCode 0021. Merge Two Sorted Lists.**
{% endhint %}

We could use the **"Merge with Divide and Conquer"** method for better performance. Generally speaking, we do merge starting with 2 lists per iteration, then increasing to 4 lists per iteration, etc.
{% endtab %}

{% tab title="🎨 Diagram Explanation" %}

```python
# size = 1, len = 5
# for i in range(0, len - size, size * 2)
# i = 0, 2, 4
# merge input = [0, 1] [2, 3] [4, 5]
['l0', l1, 'l2', l3, 'l4']
   |  /      |  /      |
   | /       | /       |
   |/        |/        |
   l0        l2       l4

# size = 2, len = 5
# for i in range(0, len - size, size * 2)
# i = 0
# merge input = [0, 2]
['l0', l1, l2, l3, l4]
   |        /       |
   |-------*        |
   l0              l4
   
# size = 4, len = 5
# for i in range(0, len - size, size * 2)
# i = 0
# merge input = [0, 4]
['l0', l1, l2, l3, l4]
   |                /
   |---------------*
   l0
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title=" 🤖 Python3" %}

```python
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # (base case)
        if len(lists) == 0: return None
        if len(lists) == 1: return lists[0]
        
        # ==================================================
        #  Linked List + Sort                              =
        # ==================================================
        # time  : O(nlogk)
        # space : O(1)
        # 
        # n is the total number of nodes in two linked lists
        # k is the number of linked lists
        
        size = 1
        while size < len(lists):
            for i in range(0, len(lists) - size, size * 2):
                lists[i] = self.merge2Lists(lists[i], lists[i+size])
            size *= 2
            
        return lists[0]
        
    def merge2Lists(self, l1: ListNode, l2: ListNode) -> ListNode:
        ret = ListNode(0)
        cur = ret
        
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = ListNode(l1.val)
                cur = cur.next
                l1 = l1.next
            else:
                cur.next = ListNode(l2.val)
                cur = cur.next
                l2 = l2.next
                
        cur.next = l1 or l2
                
        return ret.next

```

{% endtab %}

{% tab title=" 🤖 Java" %}

```java
class Solution {
    /**  
     * @time  : O(nlogk)
     * @space : O(1)
     */

    public ListNode mergeKLists(ListNode[] lists) {
        /* base case */
        if(lists.length == 0) return null;
        if(lists.length == 1) return lists[0];
        
        int size = 1;
        while(size < lists.length) {
            for(int i=0 ; i<lists.length-size ; i+=size*2) {
                lists[i] = merge2Lists(lists[i], lists[i+size]);
            }
            size *= 2;
        }
        return lists[0];
    }
    
    public ListNode merge2Lists(ListNode l1, ListNode l2) {
        ListNode ret = new ListNode(0);
        ListNode cur = ret;
        
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                cur.next = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                cur.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            cur = cur.next;
        }
        
        cur.next = (l2 == null) ? l1 : l2;
        
        return ret.next;
    }
}

```

{% endtab %}
{% endtabs %}