题目描述

给你两个非空链表，分别表示两个非负整数。表示方法：链表中的每个节点，分别表示整数中的一位数字，顺序从低位至高位。例如：2 -> 4 -> 3 表示342. 请计算两个整数的和，并返回成链表的形式。
数据保证两个整数均不包含前导0（除了0之外），例如：不会出现0023.

样例

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
解释：342 + 465 = 807.

算法

(模拟人工加法) $O(n)$

这是道模拟题，模拟我们小时候列竖式做加法的过程：

1. 从最低位至最高位，逐位相加，如果和大于等于10，则保留个位数字，同时向前一位进1.
2. 如果最高位有进位，则需在最前面补1.

做有关链表的题目，有个常用技巧：添加一个虚拟头结点：ListNode *head = new ListNode(-1);，可以简化边界情况的判断。
时间复杂度：由于总共扫描一遍，所以时间复杂度是 $O(n)$.

C++ 代码

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) 
    {
        ListNode *res = new ListNode(-1);   //添加虚拟头结点，简化边界情况的判断
        ListNode *cur = res;
        int carry = 0;  //表示进位
        while (l1 || l2) 
        {
            int n1 = l1 ? l1->val : 0;
            int n2 = l2 ? l2->val : 0;
            int sum = n1 + n2 + carry;
            carry = sum / 10;
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        if (carry) cur->next = new ListNode(1); //如果最高位有进位，则需在最前面补1.
        return res->next;   //返回真正的头结点
    }
};