Leetcode 21. Merge two ordered linked lists

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

1, 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]Copy the code

Example 2:

Input: L1 = [], L2 = [] output: []Copy the code

Example 3:

Input: L1 = [], L2 = [0] output: [0]Copy the code

Tip:

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

2, train of thought

See the linked list in the problem

What is recursion? A function that calls itself at run time is called a recursive function, and the calling process is called recursion. For example, if f(x)=x+f(x-1)f(x)=x+f(x−1) :

If I plug in f(2)

  • Return 2 + f (1)
  • Call f (1)
  • Return 1 + f (0)
  • Call f (0)
  • Return 0 + f (1)

The program will run endlessly until it crashes. If we add a statement x > 0:

Let’s talk about the following ideas:

  • Termination condition: When both lists are empty, we have merged the lists.
  • How to recurse: We determine which l1 or L2 header is smaller, and then the next pointer on the smaller node points to the merging result of the rest. (Call recursion)

Less nonsense ~~~~~ on the code!

3, code,

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; }} * * /
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null)  return l2;
        if(l2 == null)  return l1;
​
        if(l1.val>=l2.val){
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }else{
            l1.next = mergeTwoLists(l1.next,l2);
            returnl1; }}}Copy the code

4, summarize

This topic is more basic algorithm questions, for the linked list related knowledge of the examination, this question can not go to see the linked list of the basic article to understand some knowledge of the linked list.

❤️ from the LeetCode Basic Algorithms column subscribe to ❤️

The original intention of the director to write blog is very simple, I hope everyone in the process of learning less detours, learn more things, to their own help to leave your praise 👍 or pay attention to ➕ are the biggest support for me, your attention and praise to the director every day more power.

If you don’t understand one part of the article, you can reply to me in the comment section. Let’s discuss, learn and progress together!

21. Merge two ordered lists – LeetCode (leetcode-cn.com)