This is the 21st day of my participation in the August Text Challenge.More challenges in August

The title

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.

 

Example 1:

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

Output:,1,2,3,4,4 [1]

Example 2:

Input: L1 = [], l2 = []

Output: []

Example 3:

Input: L1 = [], l2 = [0]

Output: [0]

 

Tip:

  • The number of nodes in two linked lists ranges from[0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2All pressNondecreasing orderarrangement

Their thinking

Idea 1

  • Tags: linked lists, recursion
  • This problem can be achieved using recursion, and new lists do not require the construction of new nodes, so here are three elements of recursion
  • Termination condition: The two linked lists are namedl1 和 l2whenl1Is empty orl2Is null
  • Return value: Each layer call returns the sorted list header
  • This level of recursion content: ifl1 的 valIf the value is smaller, thenl1.nextWith the head of the sorted list,l2In the same way
  • O (m + n) O (m + n) O (m + n), MMMl1The length of, NNN isl2The length of the

code

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}* /
var mergeTwoLists = function(l1, l2) {
    if(l1 === null) {return l2;
    }
    if(l2 === null) {return l1;
    }
    if(l1.val < l2.val){
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }else{
        l2.next = mergeTwoLists(l1, l2.next);
        returnl2; }};Copy the code

Idea 2

Our task is to merge two ascending lists into a new ascending list.

This is like, when the military training, there are two groups, each group is according to the height, from left to right standing.

At this time, the instructor let us two groups, merge into a group, and also according to the height to stand.

At this time, do you feel the title, a little temperature, the world, and full of sunshine?

Following your feelings, let’s imagine how to properly merge into a group, as follows:

  1. First, we named the groups AAA and BBB, the CCC group of the new combination.
  2. Compare the height of the person standing at the front of the AAA group and the person standing at the front of the BBB group. The short person comes out first and stands first in the CCC group.
  3. Then the height of the people at the beginning of the two groups was compared again, and the short one came out in second place in the CCC group.
  4. And so it went on and on. Finally, all the people from ABABAB and ABAB joined the CCC group, and our task was done.

Graphical presentation

code

var mergeTwoLists = function(l1, l2) {
    if(! l1)return l2;
    if(! l2)return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        returnl2; }};Copy the code

The last

I dreamed of traveling with swords

Look at the prosperity of the world

Young heart always some frivolous

Just a man after all

No regrets I go my way

“Front-end brush” No.21