Merge k Sorted Lists

LeetCode 23 | Difficulty: Hard

Hard

Problem Description

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.

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

Topics: Linked List, Divide and Conquer, Heap (Priority Queue), Merge Sort

---

Approach

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: C# (Best: 193 ms)

Metric	Value
Runtime	193 ms
Memory	N/A
Date	2017-08-07

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        return partition(lists, 0, lists.Length-1);
    }
    public ListNode partition(ListNode[] lists, int low, int high)
    {
        if (low == high) return lists[low];
        if (low < high)
        {
            int mid = low+(high-low)/2;
            ListNode l1 = partition(lists,low,mid);
            ListNode l2 = partition(lists, mid+1, high);
            return MergeLists(l1, l2);
        }

        return null;
    }

    ListNode MergeLists(ListNode l1, ListNode l2)
    {
        ListNode dummy = new ListNode(Int32.MaxValue);
        ListNode tail = dummy;
        if (l1 == null && l2 != null) return l2;
        if (l1 != null && l2 == null) return l1;

        while (l1 != null && l2 != null)
        {
            if (l1.val <= l2.val)
            {
                tail.next = l1;
                l1 = l1.next;
            }
            else
            {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        tail.next = (l1 == null) ? l2 : l1;
        return dummy.next;
    }
}

---

Complexity Analysis

Approach	Time	Space
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.