# Merge $k$ Sorted [[linked-list|Lists]]
## Solution 1: Merge One by One
- Complexity: $O(kN)$, extreme case is [[insertion-sort]].
## Solution 2: Compare One by One
- Similar to [[leetcode/merge-two-sorted-lists|merge-two-sorted-lists]], but finds the `min_node` in all $k$ lists.
- Complexity: $O(kN)$
```python
curr = prehead = ListNode(0)
lists = [node for node in lists if node]
while lists:
min_node = min(lists, key=lambda node: node.val)
min_idx = lists.index(min_node)
curr.next = min_node
if not min_node.next:
lists.pop(min_idx)
else:
lists[min_idx] = min_node.next
curr = curr.next
return prehead.next
```
## Solution 3: [[heap|Min-Heap]]
```python
class HeapNode:
def __init__(self, node):
self.node = node
def __lt__(self, other):
# Define comparison based on ListNode's value
return self.node.val < other.node.val
def mergeKLists(lists):
dummy = ListNode(0)
current = dummy
heap = []
# Initialize the heap
for l in lists:
if l:
heapq.heappush(heap, HeapNode(l))
# Extract the minimum node and add its next node to the heap
while heap:
heap_node = heapq.heappop(heap)
node = heap_node.node
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, HeapNode(node.next))
return dummy.next
```