Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

A: hi! ~ Hello, everyone, I am YK bacteria 🐷, a front-end microsystem ✨, like to share their small knowledge 🏹, welcome to follow me 😘 ~ [wechat account: YK2012YK2012, wechat official account: ykyk2012]

Today we are going to merge two ordered linked lists. I have encountered this problem in [SPD Bank written Test]

21. Merge 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.

Link: leetcode-cn.com/problems/me…

The sample

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

[Solution 1] Iterative – non-recursive

We use a simple and understandable method first, is the iterative method, first of all, the two lists are ordered, so can be directly determine the l1 and l2 values of which a linked list of nodes are smaller, the smaller the value of the node is added to the result, when a node is added to the result, in the corresponding node in the list back.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
 
/ * * *@param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}* /
var mergeTwoLists = function (l1, l2) {
  // Create a header node with the value -1
  const prehead = new ListNode(-1);
  // Define a front pointer that starts at the head node
  let prev = prehead;
  // If both lists are not iterated, the list will continue to be iterated
  while(l1 ! = =null&& l2 ! = =null) {
    if (l1.val <= l2.val) {
      prev.next = l1;
      l1 = l1.next;
    } else {
      prev.next = l2;
      l2 = l2.next;
    }
    // The front pointer moves back
    prev = prev.next;
  }
  
  // The loop must exit because one list has already been traversed, and you just need to join the rest of the other list after the prev
  if (l1 === null) {
    prev.next = l2;
  } else{
    prev.next = l1;
  }
  
  // Return the list directly after the head node
  return prehead.next;
};
Copy the code

【 solution 2 】 Recursion

And then we’re going to implement a recursive solution

The first step is to find the recursive termination condition exit, that is, one list is empty, and directly return another list

if(l1 === null) {return l2
}else if(l2 === null) {return l1
}
Copy the code

Then make a general judgment

Determine which of the two lists’ head nodes is smaller, keep the smaller head node, and recursively call the remaining two lists

if(l1.val < l2.val){
  l1.next = mergeTwoLists(l1.next, l2)
  return l1
}
Copy the code

Take a look at the GIF below to understand

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}* /
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)
        return l2
    }
};
Copy the code