2. 两数相加

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 433 阅读时长 ≈ 1 分钟

考点

  • 链表的合并

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
	public:
		int carry = 0;
		ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
			ListNode *cur1 = l1, *cur2 = l2, *dummyHead = new ListNode(-1), *curNew = dummyHead;
			while (cur1 != nullptr || cur2 != nullptr || carry) {
				cur1 = cur1 != nullptr ? (carry += cur1->val, cur1->next) : nullptr;
				cur2 = cur2 != nullptr ? (carry += cur2->val, cur2->next) : nullptr;
				curNew->next = new ListNode(carry % 10);
				carry /= 10;
				curNew = curNew->next;
			}
			return dummyHead->next;
		}
};

思路

题目要我们算两个数相加的结果，146+854=1000；但要求的存储方式是倒过来的，641+458=0001

思路很简单：

  • 每次计算cur1+cur2+进位的和，将和求余10的值赋给新建的链表节点，将和除10的值更新进位
  • 只要cur1、cur2、进位有一个不为空，就要重复上述操作新增链表节点

若要将其改造成递归就稍有难度

  1. 子问题：计算步骤同上；还需要将每次新增的链表节点串起来

  2. 递归语句顺序：递归方向分为一去一回，去方向到达临界点后返回

    在这里，先在去方向构造完新链表节点；在回方向更新当前节点的next值，从而将链表串起来

  3. 返回值：因为只能在回方向将新链表串起，所以每次返回新节点让上一个节点更改它的next值

  4. 临界点：cur1、cur2、进位都为空

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
	public:
		int carry = 0;
		ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
			if (l1 == nullptr && l2 == nullptr && !carry) return nullptr;
			l1 = l1 != nullptr ? (carry += l1->val, l1->next) : nullptr;
			l2 = l2 != nullptr ? (carry += l2->val, l2->next) : nullptr;
			ListNode *head = new ListNode(carry % 10);
			carry /= 10;
			head->next = addTwoNumbers(l1, l2);
			return head;
		}
};

如果是99+9，到达临界点的情况如图所示；8、0、1的新建节点并没有串起来，所以才需要回方向将它们连接起来