[刷题笔记]LeetCode2. Add Two Numbers

Descripition

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
给定两个非空链表,分别表示两个逆序排列的非负整数,每个节点包含一个单一数字,求得两个整数的和并返回响应的链表表示。
假设给定的整数不会包含前导0,除非整数就是0本身。

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

分析

同时遍历两个整数链表,使用尾插法更新结果链表,新节点值为当前两节点值与前一轮进位和的个位结果,同时更新当前轮次的进位标记。

Tips:

  1. 因两整数链表长度不一定相等,为方便操作,当遍历到某个链表节点为空时,可假定其取值为0
  2. 当遍历到两个链表节点均为空时,还需检查最后的进位标志

时间复杂度和空间复杂度均为O(max(n, m)),n和m分表代表两个链表的长度。

C++ Code:

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

* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
// 为方便操作, 为结果链表构建头结点
ListNode* L = new ListNode(-1);
ListNode* p = L;

int ca = 0; // 进位标志
int v1, v2, sum, unit;
while (l1 || l2) {
v1 = l1 ? l1->val : 0;
v2 = l2 ? l2->val : 0;

sum = v1 + v2 + ca;
unit = sum % 10;
ca = sum / 10;

l1 = l1 ? l1->next : nullptr;
l2 = l2 ? l2->next : nullptr;
p->next = new ListNode(unit);
p = p->next;
}

if (ca > 0) {
p->next = new ListNode(ca);
}

return L->next;
}
};