This is the 20th day of my participation in the More text Challenge. For more details, see more text Challenge

Merge two ordered lists (Question number 21)

The title

Merge the two ascending lists into a new ascending list and return. The new list is formed by concatenating all the nodes of the given two lists.

Example 1:

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

Example 2:

Input: L1 = [], l2 = []Copy the code

Example 3:

Input: L1 = [], l2 = [0]Copy the code

Tip:

  • The number of nodes in the two linked lists ranges from[0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2All pressNon-decreasing orderarrangement

link

Leetcode-cn.com/problems/me…

explain

This one, this is a classic linked list problem.

There are two main logic of this question:

  1. What if a list is missing
  2. What is the insertion order of the nodes in the two linked lists

The first problem is easy to solve. If a list has reached its end, the result must be that the current list is connected to another list, whether the other list is null or not.

The second problem is also simple: identify the two linked head nodes, take the smaller head node and assign it to the last list to return, and then move one node back from the current list. If the heads are the same size, then I’ll just pick one of them, and WE don’t have to worry about greater than or equal, because we don’t have to worry about order.

If you understand these two points, you will find that this question is actually very simple, and the test is actually the specific implementation method.

The author here is relatively weak, although it is implemented, but the code is ugly, and no pruning.

Your own answer (iteration)

First look at the code 👇 :

var mergeTwoLists = function(l1, l2) { var head = new ListNode(0) node = head while (l1 || l2) { if ((! l1 && l2) || l2 && l1.val >= l2.val) { node.next = l2 node = node.next l2 = l2.next } else { node.next = l1 node = node.next l1 = l1.next } } return head.next };Copy the code

The overall logic and thinking is fine, the point is that at the end of a list, instead of directly assigning values to the remaining nodes, it continues to assign values foolishly, which is completely unnecessary and wasteful.

And if conditions write too complex, normal people at first glance should have to react for a while, in fact, summed up all the need to use L2 nodes, the rest of the nature is to use L1 nodes.

Is not recommended.

A Better Approach (iteration)

Let’s take a look at the official iterative solution, refreshing 👇 :

var mergeTwoLists = function(l1, l2) {
  var head = new ListNode(-1)
      node = head
  while (l1 && l2) {
    if (l1.val < l2.val) {
      node.next = l1
      l1 = l1.next
    } else {
      node.next = l2
      l2 = l2.next
    }
    node = node.next
  }
  node.next = l1 ? l1 : l2
  return head.next
};
Copy the code

Here actually the author carried on some simplification, removed! == null, directly using JavaScript implicit conversion to determine whether L1 and L2 are null.

Second, the official iteration will only be performed when L1 and L2 exist simultaneously, and the smaller of the two will be assigned.

The iteration is terminated at the end of one of the two lists, and the final assignment is performed.

A better way (recursion)

The recursive solution of this problem is more clever, unlike other problems also need to add parameters in the function ontology, only by L1 and L2 two parameters can complete the recursion 👇 :

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

If there is only one node left in the list, return the node that exists.

Here’s the big deal, where you change the next property of the smaller value node directly, assigning the value to the next recursive result. The next recursive parameter assignment changes only to the smaller list of nodes, which passes one node and leaves the other unchanged.

That’s the end of the story. It’s not too easy, it’s too easy to read the answer, but you don’t understand the truth of recursion.

It turns out that the author understands that there is an initial stage of recursion 👇 :

Well, take your time.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ