HHot 100C++ 图解

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 <= 100
  • l1 和 l2 均按 非递减顺序 排列

思路

时间O(m+n)
空间O(1)

思路

哨兵 + 每次挑较小的头结点接上。归并排序的 merge 步骤、Q23 的基础件。

图解

1 i0 2 i1 4 i2
链表结构(来自本仓库测试数据)

C++17 题解

src/07_linked_list.cpp21 行
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;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q21_merge_two_sorted9 行
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});

↑↓ 选择↵ 打开/ 随时唤起