1. Title Description

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:

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

Second, train of thought analysis

For two ascending lists, it is natural to compare the value of the head of the gate and then obtain the smallest node in order to form a new list.

Use a two-pointer variable to create two ascending lists. Initially, pointer 1 points to the head of the list and pointer 2 to the head of list 2. Then determine their values. If the value of pointer 1 is less than or equal to the value of pointer 2, insert pointer 1 into next of the new list. Pointer 1 points to next of the current node. Then start a new round of comparisons until next is null on one of them, and then add the remaining list directly to the new list and return it. If next is null for both lists, return the new list.

AC code

Method 1: Iteration

var mergeTwoLists = function(l1, l2) {
    const head = new ListNode()
    let p = head
    
    while(l1 && l2) {
        if(l1.val <= l2.val) {
            p.next = l1
            l1 = l1.next
        } else {
            p.next = l2
            l2 = l2.next
        }

        p = p.next
    }

    if(l1) p.next = l1
    else p.next = l2

    return head.next
}
Copy the code

Method 2: Recursive version

var mergeTwoLists = function(l1, l2) {
    const head = new ListNode()
    let p = head
    
    const callback = (p1, p2) => {
        if(p1 && p2) {
            if(p1.val <= p2.val) {
                p.next = p1
                p1 = p1.next
            } else {
                p.next = p2
                p2 = p2.next
            }

            p = p.next
            callback(p1, p2)
        } else if(p1) {
            p.next = p1
        } else {
            p.next = p2
        }
    }

    callback(l1, l2)

    return head.next
}
Copy the code

Four,

Mainly is the traversal of the linked list and understand the data structure of the linked list and the characteristics of the ascending sort.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign