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/