[刷题笔记]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 Solution {
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;
    }
};