Merge K ascending linked lists

  1. We can scale to multiple dimensions as we do with merging two linked lists, but to quickly compare which is smaller, use priority queues.
  2. Use merge, pairwise merge, and finally merge

But the point to consider is: How do you know which direction the pointer is moving in the same way you do when you combine two linked lists?

When you pop an element in a priority queue, the element has its own movement direction, so you can use the.next pointer to join the queue, but what if it’s not a list, it’s an array?

You can add a temporary class:

public class Node{
    int index;// Mark the array position
    int flag;// Mark which array
    int value;/ / tag values
}
Copy the code

Add each time you change the value, as follows:

Nums [][] PriorityQueue<Node> pq =new PriorityQueue<>(((o1, o2) -> o1.val-o2.val));
 List<Integer> ans = new ArrayList<>();
 while(! pq.isEmpty()){ Node cur = pq.poll(); ans.add(cur.val) cur.index++;if(cur.index<nums[cur.flag].length){ cur.val=nums[cur.flag][cur.index]; pq.offer(cur); }}Copy the code

In fact, when it comes to arrays, it’s a good idea to merge them in pairs, but the space complexity is not low and the operation is not easy. Consider the method described above.

Returning to the problem, the following is the solution to using priority queues:

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode pre = new ListNode(-1);
        ListNode tp = pre;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(((o1, o2) -> o1.val-o2.val));
        for (ListNode list : lists) {
            if(list! =null) pq.offer(list);
        }
        while(! pq.isEmpty()) { ListNode cur = pq.poll(); tp.next = cur;if(cur.next ! =null) pq.offer(cur.next);
            tp = tp.next;
            tp.next = null;
        }
        return pre.next;
    }
Copy the code