Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

1. Title Description

You are given an array of linked lists, each of which has been sorted in ascending order.

Please merge all lists into one ascending list and return the merged list.

Example 1:

Input: lists = [].enlighened by [1 4], [2, 6]] output:,1,2,3,4,4,5,6 [1] : list array is as follows: [1 - > > 5, 4-1 - > 3 - > 4, 6] 2 - > merge them into an ordered list. 1 - > 1 - > 2 - > 3 - > 4 - > 4 - > 5 - > 6Copy the code

Example 2:

Input: Lists = [] Output: []Copy the code

Example 3:

Input: Lists = [[]] Output: []Copy the code


  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • Lists [I] are in ascending order
  • Lists [I]. Length the sum does not exceed 10^4

Second, train of thought analysis

First of all, we can get two pieces of information from the title information:

  1. There are multiple linked lists, and the number of linked lists is not fixed
  2. The nodes in each list are ordered and in ascending order

Then we can see that if we want to merge all the lists, each list has a pointer, each comparison takes the smallest node of all the lists, adds it to the new list, and then moves the pointer back one bit, and then starts the next round of comparison… Repeat until all the linked list elements are added to the new list…

There is an important point here, is how to get the smallest nodes of these lists?

The simplest and most violent method is to compare all Pointers to the node to get the minimum value, but cyclic comparison is a time-consuming operation that may time out if done this way.

Is there a more elegant way to do it?

So you have to think about, can you cache the results of every comparison, can you get the minimum value from the cache? There is definitely a heap in a data structure, and we can use the small top heap to get the smallest node for each round of comparison.

The heap has a wrapper class in Java that we can use directly, the priority queue, and we can implement the comparison method and decide whether this is a small top heap or a large top heap.

Code implementation

class Solution {
  // Implement a comparator to compare the values of nodes
    static Comparator<ListNode> comparator = new Comparator<ListNode>() {
        public int compare(ListNode e1, ListNode e2) {
            returne1.val - e2.val; }};public ListNode mergeKLists(ListNode[] lists) {
      // Implement small top heap
        PriorityQueue<ListNode> queue = new PriorityQueue<>(comparator);
        ListNode ans = new ListNode();
        ListNode moveNode = ans;
        // Add non-empty list head nodes to the priority queue
        for (ListNode list : lists) {
            if(list ! =null) { queue.offer(list); }}// Continue the comparison when the queue is not empty
        while(! queue.isEmpty()) { = queue.poll();if( ! =null) {
            moveNode =;
        }; }}Copy the code


  1. This kind of problem is mainly to investigate the properties of some commonly used data structures in the data structure, usually should be more familiar with, in order to better use in practice.
  2. In general, when you have a bunch of unordered data, the maximum value, the minimum value, the KTH largest value, you can give priority to the heap.