“This is the 14th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

[B] [C] [D]

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

Tip:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 ascendingarrangement
  • lists[i].lengthThe sum of does not exceed10 ^ 4

The first thing we can think of is the stupidest way

  1. Loop through the list array, find the list with the smallest head node, and retrieve that list
  2. Concatenate the node to the end of the resulting list and move the corresponding list pointer back one bit
  3. Repeat the process until each list in the list array goes to the end of the list

However, in this method, every time we get a minimum node, we need to cycle through the linked list array and compare the size of the head nodes between the linked lists. The efficiency is very low, so we give it up directly

Answer key 1

This problem is to find the lowest value of each node, connect it to the end of the result list, design the maintenance of the highest value, we can think of heap to do

Specific ideas are as follows:

  1. Create a small top heap
  2. Traverse the list array and place each nodepushLet’s go to the small top heap
  3. When the heap is not empty, the top element is removed each time to form a new linked list

The code is as follows:

Constructor (){this.arr = []; // Constructor (){this.arr = []; this.size = 0; } push(node){ this.arr.push(node); this.size++; if(this.size>1){ let cur = this.size-1, parentInd = (cur-1)>>1; while(cur>0&&this.arr[parentInd].val>this.arr[cur].val){ [this.arr[parentInd],this.arr[cur]] = [this.arr[cur],this.arr[parentInd]]; cur = parentInd,parentInd = (cur-1)>>1; } } } pop(){ if(this.empty()) return false; const res = this.arr[0] this.arr[0] = this.arr.pop(); this.size--; let cur = 0, childl = 1, childr = 2; while( (childl<this.size&&this.arr[childl].val<this.arr[cur].val)|| (childr<this.size&&this.arr[childr].val<this.arr[cur].val) ){ if(childr<this.size&&this.arr[childr].val<this.arr[childl].val){ [this.arr[cur],this.arr[childr]] = [this.arr[childr],this.arr[cur]]; cur = childr; }else{ [this.arr[cur],this.arr[childl]] = [this.arr[childl],this.arr[cur]]; cur = childl; } childl = cur*2+1,childr = cur*2+2; } return res; } empty(){return this.size === 0}} var mergeKLists = function(lists) {// Initialize small top heap const heap = new MinHeap(); // Push each node in the list array to the small top heap for(let I = 0; i<lists.length; i++){ if(lists[i]===null) continue; while(lists[i]){ heap.push(lists[i]); lists[i] = lists[i].next; } } const vhead = new ListNode(0); let cur = vhead; // When the heap is not empty, fetch the top of the heap to form the result list. heap.empty()){ cur.next = heap.pop(); cur = cur.next; } cur.next = null; return vhead.next; };Copy the code

Code submission is ok. But it took about 100ms, beating only about 60% of users

Answer key 2

We can actually solve this in a much simpler and more crude way

Specific ideas are as follows:

  1. Initialize an empty arrayarr
  2. Traverses the list array, placing the value of each node in the listval push 到 arr 中
  3. rightarrsorting
  4. According to sortedvalValue generates a linked list of results

The code is as follows:

Var mergeKLists = function(lists) {// Initialize array const arr = []; // Iterate through the list array and push the value of each node into arR for(let I = 0; i<lists.length; i++){ if(lists[i]===null) continue; while(lists[i]){ arr.push(lists[i].val); lists[i] = lists[i].next; }} // arr sort sort arr.sort((a,b) => a-b) const vhead = new ListNode(0); let cur = vhead; for(let i = 0; i<arr.length; i++){ cur.next = new ListNode(arr[i]) cur = cur.next; } return vhead.next; };Copy the code

After the code was submitted, the user passed about 90ms, beating 90% of the users

At this point we are done with Leetcode -23- merging K ascending lists

If you have any questions or suggestions, please leave a comment!