21. 合并两个有序链表
一句话套路哨兵头结点 + 逐一接较小者
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = [] 输出:[]
示例 3:
输入:l1 = [], l2 = [0] 输出:[0]
提示:
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
思路
时间
O(m+n)空间
O(1)思路
哨兵 + 每次挑较小的头结点接上。归并排序的 merge 步骤、Q23 的基础件。
图解
链表结构(来自本仓库测试数据)
C++17 题解
namespace lc0021 {
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (l1 && l2) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2; // 剩下的整段直接接上
return dummy.next;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0021::Solution s;
ListNode* a = buildList({1, 2, 4});
ListNode* b = buildList({1, 3, 4});
CHECK_EQ(listToVec(s.mergeTwoLists(a, b)), vector<int>{1, 1, 2, 3, 4, 4});
ListNode* c = buildList({});
ListNode* d = buildList({});
CHECK_TRUE(s.mergeTwoLists(c, d) == nullptr);
ListNode* e = buildList({5});
CHECK_EQ(listToVec(s.mergeTwoLists(nullptr, e)), vector<int>{5});