Skip to main content

🟥 Merge k Sorted Lists (#23)

🔗 Problem Link​

📋 Problem Statement​

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.

💡 Examples​

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: []

🔑 Key Insights & Approach​

Core Observation: Use divide and conquer (merge pairs) or min heap to efficiently find minimum among k lists.

Why Min Heap or Divide & Conquer?

  • Heap: O(N log k) where N = total nodes
  • Divide & Conquer: O(N log k)
  • Better than merging sequentially: O(kN)

Approaches:

  1. Sequential merge: O(kN)
  2. Min Heap: O(N log k) - good for streaming
  3. Divide & Conquer: O(N log k) - optimal for in-memory

Pattern: "Merge K Sorted" using heap or divide and conquer.

🐍 Solution: Python​

Approach 1: Min Heap​

Time Complexity: O(N log k) | Space Complexity: O(k)

from typing import List, Optional
import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

        # Add first node from each list
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))

        dummy = ListNode(0)
        current = dummy

        # Process heap
        while heap:
            val, i, node = heapq.heappop(heap)
            current.next = node
            current = current.next

            # Add next node from same list
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))

        return dummy.next

Approach 2: Divide and Conquer​

Time Complexity: O(N log k) | Space Complexity: O(1)

from typing import List, Optional

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None

        while len(lists) > 1:
            merged = []

            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None
                merged.append(self.merge2Lists(l1, l2))

            lists = merged

        return lists[0]

    def merge2Lists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        current = dummy

        while l1 and l2:
            if l1.val <= l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next

        current.next = l1 if l1 else l2
        return dummy.next

🔵 Solution: Golang​

Approach: Divide and Conquer​

Time Complexity: O(N log k) | Space Complexity: O(1)

type ListNode struct {
    Val  int
    Next *ListNode
}

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }

    for len(lists) > 1 {
        merged := []*ListNode{}

        for i := 0; i < len(lists); i += 2 {
            l1 := lists[i]
            var l2 *ListNode
            if i+1 < len(lists) {
                l2 = lists[i+1]
            }
            merged = append(merged, merge2Lists(l1, l2))
        }

        lists = merged
    }

    return lists[0]
}

func merge2Lists(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    current := dummy

    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            current.Next = l1
            l1 = l1.Next
        } else {
            current.Next = l2
            l2 = l2.Next
        }
        current = current.Next
    }

    if l1 != nil {
        current.Next = l1
    } else {
        current.Next = l2
    }

    return dummy.Next
}

📚 References​