This is the 18th day of my participation in Gwen Challenge

Topic describes

Merges 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. Leetcode-cn.com/problems/me…

/ / sample 1Input: l1 = [1.2.4], l2 = [1.3.4] output: [1.1.2.3.4.4]
/ / sample 2Input: L1 = [], l2 = [0] output: [0]
Copy the code

The label

recursive

Analysis of the problem solving

1. The recursion

Let’s get right to it.

This can be easily solved by direct recursion. Suppose we pass in two linked lists [1.2.4], [1.3.4The most important thing to note is the value comparison of linked list nodes. Judge the first node in the list first, because it is an ordered list merge and it is correct to have the smallest node first. The smaller of the two first nodes, the next of which is equal to the return value of the recursive function. Here the recursive function is passing in the first node and comparing the larger node with the smaller node and continuing the recursion. Then return the smaller node. This might be a little bit of a detour of the code.Copy the code

Go to ！！！！！

/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val? : number, next? : ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null) :ListNode | null {
    // If the incoming list does not exist, the second list is returned
    if(l1 === null) return l2 
    else if(l2 === null) return l1 
    // Determine the value of the two nodes, return the smaller node, and let the next small node continue recursively.
    else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1 
    }
    // Same logic as above, always return small nodes and recurse.
    else {
        l2.next = mergeTwoLists(l1, l2.next)
        return l2 
    }
};
Copy the code

The last

From today not pigeon, every day an algorithm problem and published articles, first want to solve the problem group for Top100, the tenth topic finished work!!