“This is the ninth day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

At least one algorithm every day, dead beat algorithm

Today we finally started to learn the linked list, linked list problems are really not that easy to master, I mean the master is

  • Write it down in 10 minutes
  • Write in Leetcode without code prompts
  • And I can write it right in 2 times

So we do a good job in the heart, don’t be hit, we must have a dead knock spirit

For our convenience to master, so we discuss the linked list skills

Start with a simple topic and a starter

The title

This is problem number 21 on Leetcode – merging two ordered lists

Merges two ascending lists into a new ascending list and returns. A new list is formed by concatenating all the nodes of a given two lists.

Difficulty: Easy

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]Copy the code

Train of thought

We have done a similar array problem, js algorithm problem solving (day 2)– LeetCode: 88. Combine two ordered arrays, which are very similar except for their data structures

So the solution is also very similar

Back then, arrays started looping from the back, but lists were hard to loop from the back, so we started looping from the front

So the linked list cycle we must be very skilled master

List cycle

let dummy = new ListNode();
// cur is equivalent to dummy. We are defining a variable called cur because the result is to return the entire list, so return dummy.next
let cur = dummy;

while(cyclic condition){// each time cur points to a new node
    cur=cur.next;
}
return dummy.next;

Copy the code

As long as you keep in mind the above loop, the single-linked list problem is easy to solve

Extract key words from the topic

  • 1. Merge into a new ascending linked list, so we need to create a new linked list variable. Ascending represents the size of the two linked list nodes given in the question
  • 2. The new linked list assigns values from l1 and L2 to new nodes through a loop

Answer key

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}* /
var mergeTwoLists = function(l1, l2) {
     // Define dummy node
    let dummy = new ListNode();
    // cur is equivalent to dummy. We are defining a variable called cur because the result is to return the entire list, so return dummy.next
    let cur = dummy;
    // l1,l2 is equivalent to two Pointers, l1&&l2 is the end of the loop condition
    while(l1&&l2){
        // Compare pointer values
        if(l1.val>l2.val){
            cur.next = l2;
            // Change the variable, cur.next will not change the direction
            l2 = l2.next;
        }else {
            cur.next = l1;
            l1 = l1.next;
        }
        // cur reassigns the value
        cur=cur.next;
    }
    // If the list is not null, cur.next points to itcur.next=(l1? l1:l2);return dummy.next;
};
Copy the code

conclusion

Circular linked list must be well mastered, only in this way, we can better tear algorithm, refueling ah, old iron people