HHot 100C++ 图解

2. 两数相加

中等 链表 在力扣上做

一句话套路逐位相加,哨兵结点简化尾插

题目描述

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

 

示例 1:

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.

示例 2:

输入:l1 = [0], l2 = [0]
输出:[0]

示例 3:

输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]

 

提示:

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

思路

时间O(max(m,n))
空间O(1)(输出不计)

思路

竖式加法。链表已经是低位在前,正好顺序遍历。

循环条件用 carry || (l1 || l2),否则 [9,9] + [1] 会丢掉最高位的进位。

对比

Q445 逆序/正序之分就在于要不要先反转或借助栈。

图解

9 i0 9 i1 9 i2 9 i3 9 i4 9 i5 9 i6
链表结构(来自本仓库测试数据)

C++17 题解

src/07_linked_list.cpp19 行
namespace lc0002 {
class Solution {
 public:
  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    int carry = 0;
    while (l1 || l2 || carry) {
      int sum = carry + (l1 ? l1->val : 0) + (l2 ? l2->val : 0);
      carry = sum / 10;
      tail->next = new ListNode(sum % 10);
      tail = tail->next;
      if (l1) l1 = l1->next;
      if (l2) l2 = l2->next;
    }
    return dummy.next;
  }
};
}

单元测试

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

TEST q2_add_two_numbers10 行
lc0002::Solution s;
ListNode* a = buildList({2, 4, 3});
ListNode* b = buildList({5, 6, 4});
CHECK_EQ(listToVec(s.addTwoNumbers(a, b)), vector<int>{7, 0, 8});  // 342+465=807
ListNode* c = buildList({9, 9, 9, 9, 9, 9, 9});
ListNode* d = buildList({9, 9, 9, 9});
CHECK_EQ(listToVec(s.addTwoNumbers(c, d)), vector<int>{8, 9, 9, 9, 0, 0, 0, 1});
ListNode* e = buildList({0});
ListNode* f = buildList({0});
CHECK_EQ(listToVec(s.addTwoNumbers(e, f)), vector<int>{0});

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