---
title: '23. Merge k Sorted Lists'
description: You are given an array of k linked-lists lists, each linked-list is sorted in ascending order
sidebar:
  label: 'Merge k Sorted Lists'
  badge: 'Hard'
---

Linked List

### 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 linked 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 <= 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 will not exceed 10^4.

## Approach

```mermaid
flowchart TD
  S(["mergeKLists(lists)"]) --> I["heap = []"]
  I --> F{"more i, node in enumerate(lists)?"}
  F -- yes --> C{"node?"}
  C -- yes --> P["heapq.heappush(heap, (node.val, i, node)) — i breaks ties so nodes are never compared"]
  P --> F
  C -- no --> F
  F -- no --> D["D = ListNode(), cur = D"]
  D --> W{"heap?"}
  W -- no --> E(["return D.next"])
  W -- yes --> O["val, i, node = heapq.heappop(heap) — the smallest head across all lists"]
  O --> L["cur.next = node, cur = node, node = node.next"]
  L --> N{"node?"}
  N -- yes --> Q["heapq.heappush(heap, (node.val, i, node))"]
  Q --> W
  N -- no --> W
```

## Solution

```py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq


class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []

        # K log K
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))

        D = ListNode()
        cur = D

        # n log k
        while heap:
            val, i, node = heapq.heappop(heap)
            cur.next = node
            cur = node
            node = node.next

            if node:
                heapq.heappush(heap, (node.val, i, node))

        # Time: O(N log k)
        # Space: O(n)
        return D.next
```

## Explanation

[Merge K Sorted Lists - Leetcode 23 - Python](https://www.youtube.com/watch?v=q5a5OiGbT6Q)