[Leetcode]21. Merge Two Sorted Lists(C++)

题目描述

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.

例子

例子 1

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

例子 2

Input: `l1 = [], l2 = []` Output: `[]`

例子 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.

解题思路

``````/**
* 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* l1, ListNode* l2) {
ListNode* dummy = new ListNode();
ListNode* curr = dummy;
while (l1 && l2) {
if (l1->val <= l2->val) {
curr->next = l1;
l1 = l1->next;
}
else {
curr->next = l2;
l2 = l2->next;
}
curr = curr->next;
}

if (!l1) {
curr->next = l2;
} else if (!l2) {
curr->next = l1;
}

return dummy->next;
}
};
``````
• 时间复杂度: O(n)
• 空间复杂度: O(1)

GitHub 代码同步地址： 21.MergeTwoSortedLists.cpp

Built with Hugo
Theme Stack designed by Jimmy