---
link: https://leetcode.com/problems/merge-k-sorted-lists/
tags: linked list, singly, hard, heap
---

# 23. Merge k Sorted Lists

## Question
Merge *k* sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

**Example:**

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

## Solution: Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        from heapq import heappush, heappop
        heap = []
        dummy_node = ListNode()
        curr = dummy_node
        
        for node in lists:
            if node:
                heappush(heap, (node.val, node))
        
        while heap:
            _, node = heappop(heap)
            curr.next = node
            curr = curr.next
            
            if node.next:
                heappush(heap, (node.next.val, node.next))
                
        return dummy_node.next

## Solution: Java