题目描述
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入格式
输入共 5 行：
- 第一行包含一个整数 n，表示第一个链表的长度。
- 第二行包含 n 个整数，表示第一个链表的节点值，按链表顺序给出。
- 第三行包含一个整数 m，表示第二个链表的长度。
- 第四行包含 m 个整数，表示第二个链表的节点值，按链表顺序给出。
输出格式
输出共 1 行，包含 n+m 个整数，表示合并后的链表的节点值，按链表顺序给出。
数据范围
两个链表的节点数目范围是 [0, 50]
-100 ≤ Node.val ≤ 100
两个链表均按非递减顺序排列
输入样例1：
输出样例1：
输入样例2：
输出样例2：
输入样例3：
输出样例3：
注意事项
- 可以使用迭代或递归的方法来合并两个有序链表。
- 迭代方法的时间复杂度为O(n+m)，空间复杂度为O(1)。
- 递归方法的时间复杂度为O(n+m)，空间复杂度为O(n+m)，因为递归调用会使用栈空间。
- 在本题中，为了方便输入输出，我们将使用数组来模拟链表的输入，并将合并后的链表转换为数组输出。
代码实现
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
| #include <iostream>
#include <vector>
using namespace std;
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) {}
};
ListNode* mergeTwoListsIterative(ListNode* list1, ListNode* list2)
{
ListNode* dummy = new ListNode(-1);
ListNode* curr = dummy;
while (list1 != nullptr && list2 != nullptr)
{
if (list1->val <= list2->val)
{
curr->next = list1;
list1 = list1->next;
}
else
{
curr->next = list2;
list2 = list2->next;
}
curr = curr->next;
}
if (list1 != nullptr)
{
curr->next = list1;
}
else
{
curr->next = list2;
}
ListNode* head = dummy->next;
delete dummy;
return head;
}
ListNode* mergeTwoListsRecursive(ListNode* list1, ListNode* list2)
{
if (list1 == nullptr)
{
return list2;
}
if (list2 == nullptr)
{
return list1;
}
if (list1->val <= list2->val)
{
list1->next = mergeTwoListsRecursive(list1->next, list2);
return list1;
}
else
{
list2->next = mergeTwoListsRecursive(list1, list2->next);
return list2;
}
}
ListNode* createList(vector<int>& nums)
{
if (nums.empty()) {
return nullptr;
}
ListNode* head = new ListNode(nums[0]);
ListNode* current = head;
for (int i = 1; i < nums.size(); i++) {
current->next = new ListNode(nums[i]);
current = current->next;
}
return head;
}
vector<int> listToArray(ListNode* head)
{
vector<int> result;
ListNode* current = head;
while (current != nullptr) {
result.push_back(current->val);
current = current->next;
}
return result;
}
void deleteList(ListNode* head)
{
ListNode* current = head;
while (current != nullptr) {
ListNode* next = current->next;
delete current;
current = next;
}
}
int main()
{
int n, m;
cin >> n;
vector<int> nums1(n);
for (int i = 0; i < n; i++) {
cin >> nums1[i];
}
cin >> m;
vector<int> nums2(m);
for (int i = 0; i < m; i++) {
cin >> nums2[i];
}
ListNode* list1 = createList(nums1);
ListNode* list2 = createList(nums2);
ListNode* mergedList = mergeTwoListsIterative(list1, list2);
vector<int> result = listToArray(mergedList);
for (int i = 0; i < result.size(); i++) {
cout << result[i];
if (i != result.size() - 1) {
cout << " ";
}
}
cout << endl;
deleteList(mergedList);
return 0;
}
|
时间复杂度
- 迭代方法时间复杂度：O(n+m)，其中 n 和 m 分别是两个链表的长度。我们需要遍历两个链表各一次。
- 递归方法时间复杂度：O(n+m)，其中 n 和 m 分别是两个链表的长度。递归调用的次数等于两个链表的节点总数。
- 空间复杂度：O(1)（迭代方法）或 O(n+m)（递归方法，由递归调用栈占用的空间）。
代码解释
- 合并两个有序链表是链表操作中的一个基础问题，可以用迭代或递归的方法解决。
- 迭代方法的核心思想是使用一个指针 curr 来构建新的链表。我们同时遍历两个链表，每次选择值较小的节点加入新链表，直到遍历完其中一个链表。然后将另一个链表的剩余部分直接接到新链表的末尾。
- 递归方法的核心思想是：如果其中一个链表为空，直接返回另一个链表；否则，选择值较小的节点作为当前节点，然后递归地合并该节点的下一个节点与另一个链表。
- 在本题中，为了方便输入输出，我们使用数组来模拟链表的输入，并将合并后的链表转换为数组输出。在实际应用中，链表通常是直接给定的。