21. 合并两个有序链表(Merge Two Sorted Lists)E
英文题目
Merge two sorted linked lists and return it as a new sorted list. The new 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 <= 100
Both l1 and l2 are sorted in non-decreasing order.
中文题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4
递归法
终止条件:当两个链表都为空时,表示链表已合并完成
如何递归:判断l1和l2头结点哪个更小,然后较小结点的 next 指针指向其余结点的合并结果
时间复杂度O(m+n),空间复杂度O(m+n)
# python3: 时间 36 ms, 击败 61.73%; 内存 15.1 MB, 击败 20.34% # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if not l1: return l2 if not l2: return l1 if l1.val <= l2.val: l1.next = self.mergeTwoLists(l1.next, l2) return l1 else: l2.next = self.mergeTwoLists(l1, l2.next) return l2
// c++: 时间 8 ms, 击败 61.71%; 内存 14.4 MB, 击败 65.11% /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { if (list1 == nullptr) { return list2; } else if (list2 == nullptr) { return list1; } if (list1->val <= list2->val) { list1->next = mergeTwoLists(list1->next, list2); return list1; } else { list2->next = mergeTwoLists(list1, list2->next); return list2; } } };
// java: 时间 0 ms, 击败 100%; 内存 40.3 MB, 击败 75.16% /** * 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 list1, ListNode list2) { if (list1 == null) { return list2; } else if (list2 == null) { return list1; } if (list1.val < list2.val) { list1.next = mergeTwoLists(list1.next, list2); return list1; } else { list2.next = mergeTwoLists(list1, list2.next); return list2; } } }
// go: 时间 0 ms, 击败 100%; 内存 2.4 MB, 击败 27.85% /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode { if list1 == nil { return list2 } else if list2 == nil { return list1 } if list1.Val <= list2.Val { list1.Next = mergeTwoLists(list1.Next, list2) return list1 } else { list2.Next = mergeTwoLists(list1, list2.Next) return list2 } }
// javascript: 时间 72 ms, 击败 48.39%; 内存 43.6 MB, 击败 5.2% /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} list1 * @param {ListNode} list2 * @return {ListNode} */ var mergeTwoLists = function(list1, list2) { if (list1 == null) { return list2; } else if (list2 == null) { return list1; } if (list1.val < list2.val) { list1.next = mergeTwoLists(list1.next, list2); return list1; } else { list2.next = mergeTwoLists(list1, list2.next); return list2; } };
迭代法
基本操作
时间复杂度O(n+m),空间复杂度O(1)
# python3: 时间 32 ms, 击败 84.58%; 内存 15.1 MB, 击败 20.34% # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: dummy = ListNode(-1) cur = dummy while l1 and l2: if l1.val <= l2.val: cur.next = l1 l1 = l1.next else: cur.next = l2 l2 = l2.next cur = cur.next if l1: cur.next = l1 if l2: cur.next = l2 return dummy.next
// c++: 时间 4 ms, 击败 92.27%; 内存 14.4 MB, 击败 38.37% /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode dummy = ListNode(); ListNode * cur = &dummy; while (list1 != nullptr && list2 != nullptr) { if (list1->val <= list2->val) { cur->next = list1; list1 = list1->next; } else { cur->next = list2; list2 = list2->next; } cur = cur->next; } if (list1 != nullptr) { cur->next = list1; } if (list2 != nullptr) { cur->next = list2; } return dummy.next; // 注意此处用. } };
// java: 时间 0 ms, 击败 100%; 内存 40.5 MB, 击败 42.66% /** * 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 list1, ListNode list2) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; while (list1 != null && list2 != null) { if (list1.val < list2.val) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } cur = cur.next; } if (list1 != null) { cur.next = list1; } if (list2 != null) { cur.next = list2; } return dummy.next; } }
// go: 时间 4 ms, 击败 48.54%; 内存 2.4 MB, 击败 99.90% /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode { dummy := &ListNode{} // 注意此处的初始化 cur := dummy for list1 != nil && list2 != nil { if list1.Val <= list2.Val { cur.Next = list1 list1 = list1.Next } else { cur.Next = list2 list2 = list2.Next } cur = cur.Next } if list1 != nil { cur.Next = list1 } if list2 != nil { cur.Next = list2 } return dummy.Next }
// javascript: 时间 68 ms, 击败 69.14%; 内存 43.2 MB, 击败 40.43% /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} list1 * @param {ListNode} list2 * @return {ListNode} */ var mergeTwoLists = function(list1, list2) { let dummy = new ListNode(-1); let cur = dummy; while (list1 != null && list2 != null) { if (list1.val < list2.val) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } cur = cur.next; } if (list1 != null) { cur.next = list1; } if (list2 != null) { cur.next = list2; } return dummy.next; };