Obsidian Notes

10. Merge k Sorted Lists

3 min read

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

Approach

  • Extension of the merge 2 sorted linked list so create a method for that

  • Now we loop take 2 lists then call our method and merge then we save it to the original array so we keep making it short till only one is left

  • For the toArray() method we provide a sample array to know the type otherwise it runs into type conversion issues or you have to type cast it later

  • Time complexity is nlogk because the second loop for merging is running n times or n/2 check then the outer loop is run as we are halving each time that is why log

  • Time:O(nlogk) Space:O(k) Where k is the total number of lists and n is the total number of nodes across k lists

  • We already know how to solve the merge two lists now what we have to do is loop through the lists 2 at a time and merge the lists then our list will halved then assign this new list to the old we keep doing it till the length of the list is greater than 1 then return the 0 index

/**
 * 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;
        while (lists.length > 1) {
            List<ListNode> mer = new ArrayList<>();
            for (int i = 0; i < lists.length; i += 2) {
                ListNode a = lists[i];
                ListNode b = i + 1 < lists.length ? lists[i+1] : null;
                mer.add(m(a,b));
            }
            lists = mer.toArray(new ListNode[0]);
        }
        return lists[0];
    }
 
    public ListNode m(ListNode a, ListNode b) {
        ListNode d = new ListNode();
        ListNode c = d;
        while (a != null && b != null) {
            if (a.val < b.val) {
                c.next = a;
                a = a.next;
            } else {
                c.next = b;
                b = b.next;
            }
            c = c.next;
        }
        if (a != null) c.next = a;
        if (b != null) c.next = b;
        return d.next;
    }
}

Backlinks