This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

I’m doing my best to keep you from skipping puzzles by default.

Merge K ascending linked lists

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.

case1: Enter: lists = [[1.4.5], [1.3.4], [2.6] output: [1.1.2.3.4.4.5.6] The list array is as follows:1->4->5.1->3->4.2->6] combine them into an ordered linked list.1->1->2->3->4->4->5->6

例2: Input: Lists = [] Output: [] Example3: Input: Lists = [[]] Output: []Copy the code

First of all, see the problem first don’t panic, first think about what posture you want to use to stem this problem.

As elegant front-end learners, we first need to let ourselves be cool.

So let’s review some of the facts

The list

The pictures are from the link list of Likou Free learning for Curious Baby.

What’s sweet is a linked list, which is basically a set of objects, each with a value and a next pointer to the next object.

function ListNode(val) {
            this.val = val;
            this.next = null;
        }
Copy the code

The sorting

The sort method is used to sort the elements of an array. Syntax: arr.sort([compareFunction]) compareFunction(a,b) : used to specify functions in a certain order. If omitted, the element is sorted by the Unicode site of each character in the converted string. - 'a' - The first element used for comparison. - 'b' - The second element used for comparison. If 'compareFunction(a, b)' is less than 0, a will be placed before B. If 'compareFunction(a, b)' is equal to 0, the relative positions of a and B remain the same. If 'compareFunction(a, b)' is greater than 0, b will be placed before A. CompareFunction (a, b) must always return the same comparison on the same input, otherwise the sorting result will be indeterminate. Return value: sorted array. Note that the array is sorted in place and is not copied.Copy the code

To the problem solving

So first of all, we have to figure out what the values are

// We need a structure to hold the data fields of each list in the array.
const list = [];

// We need to add it multiple times, so create a loop.
for (let i = 0; i < lists.length; i++) {

// Then we need to add the data to the array. First we store each list in the array into a variable.
        let node = lists[i];
        
While evaluates the node passed in. When node == null, the current list is processed
        while (node) {
            list.push(node.val);
            node = node.next;
        }
// After the while loop ends, all the values of the first list are stored in the array.
}
Copy the code

Then, to keep the structure sorted, we need to sort the array at this point.


// I chose the easiest bubble sort for the front end
list.sort((a, b) = > a - b);

Copy the code

Finally, the final step is to convert the array to a linked list

// Create a header
const res = new ListNode();
let new = res;

// Loop to add data to the list
for (let i = 0; i < list.length; i++) {
        now.next = new ListNode(list[i]);
        now = now.next;
}
return res.next;
Copy the code

Finally, take a look at the entire code:

/ * * *@param {ListNode[]} lists
 * @return {ListNode}* /
var mergeKLists = function (lists) {
    const list = [];
    for (let i = 0; i < lists.length; i++) {
        let node = lists[i];
        while (node) {
            list.push(node.val);
            node = node.next;
        }
    }
    list.sort((a, b) = > a - b);
    const res = new ListNode();
    let now = res;
    // console.log(list)
    for (let i = 0; i < list.length; i++) {
        now.next = new ListNode(list[i]);
        now = now.next;
    }
    return res.next;
};
Copy the code

A difficult problem was solved in the simplest way.

But we will never rest on our laurels.

“The hymn of man is the hymn of courage, and the greatness of man is the greatness of courage!” “– William A. Zibelin

True courage is knowing what to fear and what not to fear, and to change what can be changed.

We have to explore, like generation JoJo, constantly sharpen.

Without further ado, the code

var mergeKLists = function(lists) {
    return lists.reduce((p, n) = > {
        while (n) {
            p.push(n), n = n.next
        }
        return p
    },[]).sort((a, b) = > a.val - b.val).reduceRight((p, n) = > (n.next = p, p = n, p), null)}; By Mantoufan Link: HTTPS//leetcode-cn.com/problems/merge-k-sorted-lists/solution/reduce-sort5xing-dai-ma-chao-93-by-mantoufan/Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.Copy the code

Let oneself grow first step, first have to learn the way of thinking

  • Read the big guy’s code
  • Targeted knowledge supplement
  • After learning to the big man’s ideas for code implementation

Parsing slowly, this code first uses reduce()

The reduce() method performs a reducer function (in ascending order) that you provide on each element in the array, summarizing its results into a single return value. Reducer function reception4A parameter:1.Accumulator (ACC)2.Current Value (CUR)3.Current Index (IDX)4.  Source Array(SRC) (Source array) The return value from your Reducer function is assigned to the accumulator, and this return value is remembered in each iteration of the array and becomes the final single result value. Syntax: Arr. reduce(callback(Accumulator, currentValue[, index[, array]])[, initialValue]) Returned value: Result of the cumulative processing of the functionCopy the code

In layman’s terms, Reduce can put every value in a linked list into a callback function.

So the following callback part:

(p, n) => {
// If there are n nodes, keep adding n to array p and pointing n to the next node
    while (n) {
        p.push(n), n = n.next
    }
    return p
Copy the code

After:

sort((a, b) = > a.val - b.val).reduceRight((p, n) = > (n.next = p, p = n, p), null)
Copy the code

The callback is going to return p which is an array of nodes, and we’re going to call sort of the array.

Each element of the array is a separate node (object). A. val and b.val are the values of each node.

Finally, the reduceRight() method was used

The function of the reduceRight() method is the same as that of reduce(), except that reduceRight() adds the items in the array forward from the end of the array.

The callback function in reduceRight() is to relink the next pointing of each object (node) passed in, which is equivalent to reconnecting the node objects sorted separately into a linked list.

The total

In this problem, the same idea, different code to the expression of the person is different, force button problem solving area there are many different ideas of solution, recursion + divide and conquer, double pointer…… There is no limit to learning, and I hope we can all learn for life.