LeetCode-21.Merge Two Sorted Lists | 合併兩個有序鍊表

2021-03-02 以寫作調身心
題目

LeetCode[1]
LeetCode-cn[2]

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]Output: [1,1,2,3,4,4]
Example 2:
Input: l1 = [], l2 = []Output: []
Example 3:
Input: l1 = [], l2 = [0]Output: [0]

Constraints:The number of nodes in both lists is in the range [0, 50].-100 <= Node.val <= 100Both l1 and l2 are sorted in non-decreasing order.

題解

這道題是經典的考察鍊表的題目。

解法一:遞歸

•終止條件:兩條鍊表分別名為 l1 和 l2,當 l1 為空或 l2 為空時結束•返回值:每一層調用都返回排序好的鍊表頭•本級遞歸內容:如果 l1 的 val 值更小,則將 l1.next 與排序好的鍊表頭相接,l2 同理•O(m+n)O(m+n),mm 為 l1的長度,nn 為 l2 的長度

//Go/** * Definition for singly-linked list. * type ListNode struct { *     Val int *     Next *ListNode * } */func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {    if l1 == nil {        return l2;    }else if l2 == nil {        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;    }}

執行結果:

leetcode-cn:執行用時:0 ms, 在所有 Go 提交中擊敗了100.00%的用戶內存消耗:2.6 MB, 在所有 Go 提交中擊敗了26.43%的用戶
leetcode:Runtime: 0 ms, faster than 100.00% of Go online submissions for Merge Two Sorted Lists.Memory Usage: 2.6 MB, less than 51.09% of Go online submissions for Merge Two Sorted Lists.

可以看到,該解法執行用時為0ms,非常高效。

連結

力扣-畫解算法:21. 合併兩個有序鍊表[3]

References

[1] LeetCode: https://leetcode.com/problems/merge-two-sorted-lists/
[2] LeetCode-cn: https://leetcode-cn.com/problems/merge-two-sorted-lists/
[3] 力扣-畫解算法:21. 合併兩個有序鍊表: https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/hua-jie-suan-fa-21-he-bing-liang-ge-you-xu-lian-bi/

相關焦點

  • 合併兩個有序鍊表 | Leetcode題解
    return l2作者:LeetCode-Solution連結:https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
  • LeetCode-23.合併K個排序鍊表(Merge k Sorted Lists)
    合併K個升序鍊表合併 k 個排序鍊表,返回合併後的排序鍊表。請分析和描述算法的複雜度。示例:輸入:[ 1->4->5, 1->3->4, 2->6]輸出: 1->1->2->3->4->4->5->6來源:力扣(LeetCode)連結:https://leetcode-cn.com/problems/merge-k-sorted-lists
  • LeetCode 23. Merge k Sorted Lists
    [傳送門](https://leetcode.com/problems/merge-k-sorted-lists/)## 題意
  • leetcode-21. Merge Two Sorted Lists
    題目描述(簡單難度)題目描述:將兩個升序鍊表合併為一個新的
  • LeetCode Top 100 高頻算法題 21. Merge Two Sorted Lists
    LeetCode算法題有一個技巧:先看每道題的example,大部分情況看完example就能理解題目意思;如果看完example還有疑惑,可以再回過頭來看英文題目,這樣也可以節省一點時間~Merge two sorted linked lists and return it as a
  • LeetCode鍊表合併題目解析
    leetcode鍊表合併相關題目:21_merge-two-sorted-lists1699_merge-in-between-linked-lists21_merge-two-sorted-lists1、題目描述將兩個升序鍊表合併為一個新的 升序 鍊表並返回。
  • leetcode-23. Merge k Sorted Lists
    請你將所有鍊表合併到一個升序鍊表中,返回合併後的鍊表。我們用 N表示鍊表的總長度,考慮最壞情況,k 個鍊表的長度相等,都為 n 。解法一 暴力破解簡單粗暴,遍歷所有的鍊表,將數字存到一個數組裡,然後用快速排序,最後再將排序好的數組存到一個鍊表裡。
  • ​LeetCode刷題實戰23:合併K個升序鍊表
    今天和大家聊的問題叫做合併K個升序鍊表,我們先來看題面:https://leetcode-cn.com/problems/merge-k-sorted-lists/Given an array of linked-lists lists, each linked list is sorted in ascending order.Merge
  • 算法入門必讀:Merge Two Sorted Lists(合併兩個有序鍊表)
    今天我們來討論一下如何將兩個鍊表合併的問題。我們來看一下問題的具體描述:有兩個單向鍊表,它們每個節點都有一個數字,且節點中的數字按照升序排列,現在需要合併這兩個鍊表,合併後仍然是按照升序排列。舉例如下:
  • Leetcode刷題-鍊表
    合併兩個有序鍊表難度:簡單將兩個升序鍊表合併為一個新的 升序 鍊表並返回。新鍊表是通過拼接給定的兩個鍊表的所有節點組成的。,然後將鍊表拆分為兩個部分,然後分別對兩部分遞歸調用排序,然後對排序完的兩部分進行合併,也就是21題的合併兩個有序鍊表代碼class Solution:    def sortList(self, head: ListNode) -> ListNode:        def sortFunc(head: ListNode
  • LeetCode Top 100 高頻算法題 23. Merge k Sorted Lists
    linked-list is sorted in ascending order.Merge all the linked-lists into one sorted linked-list and return it.
  • LeetCode 攻略 - 2019 年 7 月下半月匯總(100 題攻略)
    ) ✔013 - 羅馬數字轉整數(roman-to-integer) ✔014 - 最長公共前綴(longest-common-prefix) ✔020 - 有效的括號(valid-parentheses) ✔021 - 合併兩個有序鍊表(merge-two-sorted-lists) ✔026 - 刪除排序數組中的重複項(remove-duplicates-from-sorted-array
  • Crazy LeetCode — 4. Median of Two Sorted Arrays
    Median of Two Sorted Arrays[1]題目There are two sorted arrays 「nums1」 and 「nums2」 of size m and n respectively.
  • 面試官系列 - LeetCode鍊表知識點&題型總結
    Sorted Lists 【easy】題意:將兩個排序好的鍊表合併成新的有序鍊表test case:Input: 1->2->4, 1->3->4Output: 1->1->2->3->4->4解題思路: 迭代法和遞歸法。
  • Go 實現 LeetCode 全集
    /problems/two-sum/[X] Best Time to Buy and Sell Stock - https://leetcode.com/problems/best-time-to-buy-and-sell-stock/[X] Contains Duplicate - https://leetcode.com/problems/contains-duplicate
  • 給Java程式設計師的20個鍊表面試題
    如何使用棧計算兩個鍊表的和?答案:https://www.geeksforgeeks.org/sum-of-two-linked-lists/9. 如何在適當的位置反轉鍊表?答案:http://www.java67.com/2017/06/5-difference-between-array-and-linked.html10.
  • 鍊表的邏輯:Beyond CRUD
    、多個鍊表的合併,可以認為是較為複雜的」增「操作。現在我們重新回到合併問題,實際上兩個鍊表合併是一個很輕鬆愉快的操作,利用虛節點建立一個新的列表,然後一一向前比較連接即可:class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        if(l1 == null) return l2;