“Offer comes, ask friends to take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. 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 1:

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

Ii. Analysis of Ideas:

This problem is also the basic problem of computer data structure and algorithm, if I remember correctly, I should have done it, but this time I still failed to write recursion, only iteration.

Iterative method

The idea of iteration is very simple: first we maintain a prehead pointer as the head of the merged list, another prev pointer to which the new element is added, and then update the next field of the Prev.

The flow looks like this. Assume that the two lists to be merged are L1 and L2, with the l1 and L2 Pointers currently pointing to the header element, respectively

  • Both lists are ordered, hence the size of the elements we point to in L1 and L2
    • Add smaller elements to the prev
    • Prev moves back, smaller element pointer moves back
  • Repeat the process until l1 or L2 reaches the end
  • When traversal terminates, at most one of L1 and L2 is non-null. Since both lists are ordered, it means that the non-empty part at this time must contain more elements than the previous merged elements, so directly connect the non-empty list to the merged list.

The recursive method

Recursion is a real human problem. Oh no, it’s my problem!

I read the explanation, and I realized I was a pig. I was a pig. I can’t think of a recursion that simple. I’m numb.

Recursion is a sub-case, we recursively define two linked list merge operations:

  • When l1[0] < L2 [0], merge(L1 [1:], L2)
  • L2 [0] + merge(L1, L2 [1:]) when L1 [0] > L2 [0]

That is, vertices with smaller headers merge with the rest of the elements

Critical conditions: We consider recursive boundary conditions:

  • Both L1 and L2 are empty linked lists, and no operations need to be merged
  • One of l1 and l2 is empty. End of the recursion

Iii. AC Code:

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

Iv. Summary:

The recursion algorithm is so simple, but I still can’t write it. It sucks. Hopefully, I’ll be able to summarize recursion and figure out the general flow of recursion.