current position:Home>"Front end brush questions" 21. Merge two ordered linked lists

"Front end brush questions" 21. Merge two ordered linked lists

2021-08-27 06:07:51 Ming wusheng

This is my participation 8 The fourth of the yuegengwen challenge 21 God , Check out the activity details :8 Yuegengwen challenge

subject

Merge two ascending linked lists into a new Ascending Link list and return . The new linked list is made up of all the nodes of the given two linked lists . 

 

Example 1:

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

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

Example 2:

Input : l1 = [], l2 = []

Output : []

Example 3:

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

Output :[0]

 

Tips :

  • The range of the number of nodes in the two linked lists is [0, 50]
  • -100 <= Node.val <= 100
  • l1 and l2 All according to Non decreasing order array

Their thinking

Ideas 1

  • label : Linked list 、 recursive
  • This problem can be implemented recursively , The new linked list does not need to construct new nodes , Let's list three elements of recursion
  • Termination conditions : The two linked lists are named l1 and l2, When l1 Is empty or l2 It ends in space time
  • Return value : Each layer call returns the sorted chain header
  • Recursive content at this level : If l1 Of val Less valuable , Will l1.next Connect with the sorted chain header ,l2 Empathy
  • O(m+n)O(m+n)O(m+n),mmm by l1 The length of ,nnn by l2 The length of

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);
        return l2;
    }
};
 Copy code 

Ideas 2

According to the meaning , We know that our task is to merge two ascending linked lists into a new ascending linked list !

This is like comparison. , During military training , There are two groups , Each group is based on height , Standing from left to right .

Now , The instructor asked us two groups , Merge into a group , And stand according to your height .

This is the time , Do you feel the problem , It's a little hot , human , Full of sunshine again ?

Follow your feelings , Let's imagine how to correctly merge into a group , The process is as follows :

  1. First , We named the group , One group is AAA, One group is BBB, New combination CCC Group .
  2. contrast AAA Group and BBB The height of the person in front of the group now , The short one comes out first , Standing on the CCC First in the group .
  3. Then compare the height of the people at the beginning of the two groups again , The short one stood up again , Standing on the CCC Group second .
  4. Just go back and forth , Final ,ABABAB Two groups , It's all there CCC Group , Our task is finished .

Graphic demonstration

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);
        return l2;
    }
};
 Copy code 

Last

I dreamed of going to the end of the world with a sword

Take a look at the prosperity of the world

Young hearts are always a little frivolous

After all, he is just an ordinary person

No regrets. I'll go my way

「 Front end brush questions 」No.21

copyright notice
author[Ming wusheng],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2021/08/20210827060748915O.html

Random recommended