This is the fifth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

The title

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]

  • Example 2:

Input: L1 = [], L2 = [] output: []

  • Example 3:

Input: L1 = [], L2 = [0] output: [0]

 

Tip:

The number of nodes in both lists ranges from [0, 50] -100 <= node. val <= 100, both L1 and L2 are in non-descending order

Problem solving:

What is an ascending linked list?

Linked list is a common basic data structure. It is a linear list

In an ascending linked list, data is ordered by key value and ordered from smallest to largest

What is a recursive algorithm?

In computer science, a recursion algorithm is a method of solving a problem by repeatedly breaking it into subproblems of the same kind.

The easiest way to read a recursive function is not to obsess over its execution, but to trust that the recursive function will do its job. When we write a recursive function, we have to think that every step is correct, the constraints are set correctly, and every time we call it closer to the constraints, the recursive function always does the job correctly.

Consider the boundary value:

The problem requires that the new list is made up of all the nodes of a given two lists, so here’s what happens

  • If one of them is empty, the new list is equal to the other list
  • Both are empty lists, so a new list made up of them is also an empty list
  • Neither list is empty:

Judging from the values of two linked list nodes, pass the linked list with the smaller node value to the next node, while the other linked list passes the current node to continue the comparison of node values. If one of the linked list parameters in the recursive call is empty, the recursive call will exit and the linked list results will be returned layer by layer

implementation

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // If one of them is empty, the new list is equal to the other list
        if(list1 == null) {return list2;
        } else if(list2 == null) {return list1;
        } else if(list1.val < list2.val){
            // recursive call
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            // recursive call
            list2.next = mergeTwoLists(list1, list2.next);
            returnlist2; }}}Copy the code