23.Merge k Sorted Lists

Published on May 8, 2023

Merge k Sorted Lists

Question

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

Algorithm

Just traverse all the nodes one by one and add them to the priority queue and pop nodes to get the final list.

Code

/**
 * 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) {
        ListNode dummy = new ListNode();
        ListNode curNode = dummy;
        
        if (lists == null || lists.length == 0) {
            return null;
        }
        
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> (a.val - b.val));
        for (ListNode node : lists) {
            if (node != null) pq.offer(node);
        }
        
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            curNode.next = new ListNode(node.val);
            if (node.next != null) pq.offer(node.next);
            curNode = curNode.next;
        }
        return dummy.next;
    }
}

/**
 * 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) {
        // Space: O(n), Time: O(n^2);
        if (lists == null || lists.length == 0) {
            return null;
        }
        
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>((a,b) -> a.val - b.val);
        for (ListNode node: lists) {
            while (node != null) {
                pq.offer(new ListNode(node.val));
                node = node.next;
            }
        }
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (!pq.isEmpty()) {
            cur.next = pq.poll();
            cur = cur.next;
        }
        return head.next;
    }
}

The second time I tried solve this problem, I used PQ, which is a right direction, but without efficient implementation. I tried to add all the element to the pq and then retrieve them actually there is no need to du such thing. Since each list is sorted, you can let the pq handle the unsorted part, which is each list head is not sorted, so you only push the head to the pq is enough, and once they are popped, since the list is sorted, we push its next into the queue and pop up next least one.

Now the result list is empty;

Now the result list [1];

Now the result list [1,1];

Continue doing this...