23 Merge k Sorted Lists ✅¶

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

C# Solution 1¶

A Simple Solution is to initialize the result as the first list. Now traverse all lists starting from the second list. Insert every node of the currently traversed list into result in a sorted way.

Time complexity: O(N2), where N is a total number of nodes, i.e., N = kn. Auxiliary Space: O(1).

namespace Algorithms.Medium
{
  public class MergeKSortedLists
  {
    public ListNode MergeKLists(ListNode[] lists)
    {
      ListNode smallestList = null;

      if (lists.Length == 1)
      {
        return lists[0];
      }

      for (var i = 0; i < (lists.Length - 1); i++)
      {
        if (i == 0)
        {
          smallestList = MergeTwoLists(lists[i], lists[i + 1]);
        }
        else
        {
          smallestList = MergeTwoLists(smallestList, lists[i + 1]);
        }
      }

      return smallestList;
    }

    public ListNode MergeTwoLists(ListNode l1, ListNode l2)
    {
      if (l1 == null)
      {
        return l2;
      }
      else if (l2 == null)
      {
        return l1;
      }
      else if (l1.val < l2.val)
      {
        l1.next = MergeTwoLists(l1.next, l2);
        return l1;
      }
      else
      {
        l2.next = MergeTwoLists(l1, l2.next);
        return l2;
      }
    }

  }
}

Solution 2: Min heap¶

alt

Time complexity: O(nklogk) Space complexity: O(k)s

namespace Algorithms.Medium
{
  public class MergeKSortedListsUsingHeap
  {
    /// <summary>
    /// https://leetcode.com/problems/merge-k-sorted-lists/discuss/10630/C-Using-MinHeap-(PriorityQueue)-Implemented-Using-SortedDictionary
    /// </summary>
    /// <param name="lists"></param>
    /// <returns></returns>
    public static ListNode MergeKLists(ListNode[] lists)
    {
      var heap = new MinHeap();

      /// put all nodes into minimum heap first one time
      foreach (var node in lists)
      {
        if (node == null)
        {
          continue;
        }

        heap.Add(node.val, node);
      }

      ///and then build a linked list using the ascending order
      ListNode curr = null, newHead = null;

      while (heap.map.Count > 0)
      {
        var node = heap.PopMin();

        if (node.next != null)
        {
          heap.Add(node.next.val, node.next);
        }

        if (curr == null)
        {
          curr = node;
          newHead = curr;
        }
        else
        {
          curr.next = node;
          curr = curr.next;
        }
      }

      return newHead;
    }
  }
}

Solution 3: Merge Sort¶

Time complexity: O(nklogk) Space complexity: O(logk)

class Solution {
public:
  ListNode* mergeKLists(vector<ListNode*>& lists) {
    return merge(lists, 0, lists.size() - 1);
  }
private:
  ListNode* merge(vector<ListNode*>& lists, int l, int r) {
    if (l > r) return nullptr;
    if (l == r) return lists[l];
    if (l + 1 == r) return mergeTwoLists(lists[l], lists[r]);
    int m = l + (r - l) / 2;
    auto l1 = merge(lists, l, m);
    auto l2 = merge(lists, m + 1, r);
    return mergeTwoLists(l1, l2);
  }
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (l1 && l2) {
      if (l1->val > l2->val) swap(l1, l2);
      tail->next = l1;
      l1 = l1->next;
      tail = tail->next;
    }
    if (l1) tail->next = l1;
    if (l2) tail->next = l2;
    return dummy.next;
  }
};

Input¶

alt

Output¶

alt