Leetcode-21. Merging two ordered lists (day6)

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

One, foreword

👨🎓 Author: Bug Bacteria

✏️ blog: CSDN, Nuggets, etc

💌 public account: Magic House of the Circle of the Apes

🚫 special statement: original is not easy, reprint please attach the original source link and this article statement, thank you for your cooperation.

🙏 Copyright notice: part of the text or pictures in the article may come from the Internet or Baidu Encyclopedia, if there is infringement, please contact bug bacteria processing.

Hello, little friends, I am bug bacteria 👀. Gold three silver four, brush the month again. So whether you’re looking for a career change or a career change, get your act together and do the right thing 👣. So, quickly follow the pace of bug bacteria roll up ⏰, become strong from this moment ➕🧈.

In the process of reviewing articles, if you think the articles are helpful to you at all, please don’t be too mean with your likes and bravely light up the articles 👍. Your likes (collect ⭐️+ pay attention to 👨 port + message board) are the best encouragement and support for bugs on my creation path. Time does not abandon 🏃🏻♀️, nuggets stop 💕, cheer up 🏻

Ii. Title Description:

Topic:

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.

See the following example for details:

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

⭐⭐⭐

Iii. Analysis of Ideas:

This is a linked list, and I don’t know how many of you are familiar with it, but it’s pretty easy to solve. Combining two sequential linked lists can be nothing more than recursive process modeling.

Consider this topic according to the above rules, termination condition: when both lists are empty, it means that we have completed the list merge.

How do I recurse? We directly determine which header l1 or L2 is smaller, and then the next pointer on the smaller node points to the result of the merger of the other nodes. In other words, merge the smaller of the two linked list headers with the result of the remaining elements.

Part of the picture demo:

Iv. Algorithm implementation:

Recursive method _AC code

The specific algorithm code is as follows:

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); return l2; }}}Copy the code

V. Summary:

The screenshot of the recursive leetcode submission result is as follows:

Complexity analysis:

Time complexity: O(n+ M). Where n and m are the lengths of the two lists respectively.
Space complexity: O(n + m). Where n and m are the lengths of the two lists respectively.

Another key point is that if either list is empty, the recursion ends.

Furthermore, there are thousands of ways to solve the problem. If you have any better ideas or ideas, please let me know in the comment section. We can learn from each other and grow faster.

Well, that’s all for this episode and I’ll see you next time.

Six, the previous recommendation:

Leetcode -1. Sum of two numbers
Leetcode – 9. Palindrome
Leetcode -13. Roman numeral to integer
Leetcode -14. The longest public prefix
Leetcode -20. Valid parentheses

. .

Vii. End of article:

If you want to learn more, check out bug Bug’s LeetCode Problem of the Day column! Take you to brush together. One person may feel very tired and difficult to persist in brushing, but a group of people will think it is a meaningful thing to brush, urge and encourage each other, and become stronger together.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

☘️ Be who you want to be, there is no time limit, you can start whenever you want,

🍀 You can change from now on, you can also stay the same, this thing, there are no rules to speak of, you can live the most wonderful yourself.