Scale Engineer

Merge k Sorted Lists

Hard
#0023Time: O(k * N)Space: O(1)41 companies
Algorithms
Divide and ConquerMerge Sort
Data structures
Linked ListHeap (Priority Queue)
Companies
AdobeAirbnbAmazonApple

Prompt

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 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 <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 104.

Approaches

4 approaches with complexity analysis and trade-offs.

This approach involves iteratively merging two lists at a time. We start with an empty list or the first list in the array, and then sequentially merge it with every other list in the input array until all lists are combined. This leverages the solution for the "Merge Two Sorted Lists" problem.

Algorithm

  • Handle the edge case where the input array lists is empty or null.
  • Initialize a ListNode called mergedList to lists[0].
  • Iterate through the lists array from the second element (i = 1) to the end.
  • In each iteration, call a helper function mergeTwoLists to merge the current mergedList with lists[i].
  • Update mergedList with the result of the merge.
  • Return mergedList after the loop finishes.

Walkthrough

We initialize our result list, let's call it mergedList, with the first list from the input array (lists[0]). Then, we loop through the rest of the lists in the array, from the second list (lists[1]) to the last one. In each iteration, we merge the current mergedList with the current list from the array (lists[i]) using a helper function that merges two sorted linked lists. The result of this merge operation becomes the new mergedList. After iterating through all the lists, mergedList will contain all the nodes from all the input lists, sorted in ascending order. The helper function mergeTwoLists works by creating a dummy head for the new list and using two pointers to traverse the two input lists, always picking the smaller node to append to the new list.

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public ListNode mergeKLists(ListNode[] lists) {        if (lists == null || lists.length == 0) {            return null;        }                ListNode mergedList = lists[0];        for (int i = 1; i < lists.length; i++) {            mergedList = mergeTwoLists(mergedList, lists[i]);        }                return mergedList;    }     private ListNode mergeTwoLists(ListNode l1, ListNode l2) {        ListNode dummyHead = new ListNode(0);        ListNode current = dummyHead;                while (l1 != null && l2 != null) {            if (l1.val < l2.val) {                current.next = l1;                l1 = l1.next;            } else {                current.next = l2;                l2 = l2.next;            }            current = current.next;        }                if (l1 != null) {            current.next = l1;        } else {            current.next = l2;        }                return dummyHead.next;    }}

Complexity

Time

O(k * N)

Space

O(1)

Trade-offs

Pros

  • Low space complexity.

  • Relatively easy to implement if you already have a function to merge two sorted lists.

Cons

  • Inefficient time complexity, especially when k is large. It repeatedly traverses the growing merged list.

Solutions

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode MergeKLists ( ListNode [] lists ) { int n = lists . Length ; if ( n == 0 ) { return null ; } for ( int i = 1 ; i < n ; ++ i ) { lists [ i ] = MergeTwoLists ( lists [ i - 1 ], lists [ i ]); } return lists [ n - 1 ]; } private ListNode MergeTwoLists ( ListNode l1 , ListNode l2 ) { ListNode dummy = new ListNode (); ListNode cur = dummy ; while ( l1 != null && l2 != null ) { if ( l1 . val <= l2 . val ) { cur . next = l1 ; l1 = l1 . next ; } else { cur . next = l2 ; l2 = l2 . next ; } cur = cur . next ; } cur . next = l1 == null ? l2 : l1 ; return dummy . next ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem