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

📢 preface

  • 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continues to punch card 12 days 🎈!
  • 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻 🌻

🌲 Example of original problem

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.

The sample1: Input: l1 = [1.2.4], l2 = [1.3.4] output: [1.1.2.3.4.4]
Copy the code
The sample2: input: l1 = [], l2 = [] Output: []Copy the code
The sample3: input: l1 = [], l2 = [0] output: [0]
Copy the code

Tip:

  • twoThe listThe range of the number of nodes of
  • -100 <= Node.val <= 100
  • Both L1 and L2Nondecreasing orderarrangement

🌻C# method 1: recursion

Thinking analytical

We can recursively define theta in both listsmergeActions (ignore boundary cases, such as empty lists, etc.) :In other words, twoThe list header value is smallOf a node with the remaining elementsmergeMerge operation results.

We directly model the above recursive process, taking into account the boundary cases.

If L1 or L2 is an empty list to begin with, then no operations need to be merged, so we just need to return a non-empty list.

Otherwise, we need to determine which of the list’s first nodes has a smaller value, L1 or L2, and recursively decide which node to add to the result next.

If either list is empty, the recursion ends.

Code:

public class Solution {
    public ListNode MergeTwoLists(ListNode l1, ListNode 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

The execution result

By execution time:80Ms, in all C# beat 97.08% of users in submissionMemory consumption:25.7MB, in all C# beat 81.30% of users in submission
Copy the code

Complexity analysis

Time complexity: O(n+m) Space complexity: O(n+m)Copy the code

🌻Java Method 1: Recursion

The solution is the same as C#, the code is different

code

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode 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

The execution result

By execution time:0Ms, beat out all Java commits100% user memory consumption:37.6MB, beat out all Java commits89.42% of the userCopy the code

Complexity analysis

Time complexity: O(n+m) Space complexity: O(n+m)Copy the code

🐢 recursive problem

But there’s a problem with recursion

Recursive solutions always give people a sense of “can not be explained”, the code is easy to understand, write their own hands will be frozen, very uncomfortable.

To trace the reasons, one is that we do not practice enough, and the other is that we do not understand enough. Still want a lot of practice refueling ability line!

The function that calls itself at run time is calledRecursive function, the invoked procedure is calledrecursive.

For example, define the function f(x)=x+f(x−1).

💬 summary

  • Today is the twelfth day of the buckle algorithm clocking!
  • This paper uses C# and Java programming languages to solve the problem
  • Sometimes some methods are written by the god of reference force buckle, but also while learning and sharing, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!