0%

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

题目描述

题目链接:21. Merge Two Sorted Lists

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.

解题思路

由于两个链表都已经排好序,所以只需要用两个指针指向两个链表,每次比较两个节点,并将当前节点指向较小的那一个(如果其中一个为空则指向另一个)即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* 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* 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

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions