精选力扣500题第23题 LeetCode 2. 两数相加【c++详细题解】

喜欢ヅ旅行 2021-07-24 16:42 384阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路
         *  3、代码

### 1、题目 ###

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

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

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

**示例 1：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

输入：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`
 *  题目数据保证列表表示的数字不含前导零

### 2、思路 ###

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

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

**具体实现**

1.  同时从头开始枚举两个链表，将`l1`和`l2`指针指向的元素相加存到`t`中，再将`t % 10`的元素存到`dummy`链表中，再`t / 10`去掉存进去的元素，`l1`和`l2`同时往后移动一格
2.  当遍历完所有元素时，如果`t != 0`，再把`t`存入到`dummy`链表中

做有关链表的题目，有个常用技巧：添加一个虚拟头结点：`ListNode *head = new ListNode(-1)`;，可以简化边界情况的判断。

**时间复杂度**：由于总共扫描一遍，所以时间复杂度是  O ( n ) O(n) O(n).

### 3、代码 ###

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
    class Solution { 
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { 
            ListNode* dummy = new ListNode(-1); //虚拟头结点
            ListNode* cur = dummy;
            int t = 0; //存贮进位
            while(l1 || l2 || t)
            { 
                if(l1) t += l1->val,l1 = l1->next;
                if(l2) t += l2->val,l2 = l2->next;
                cur = cur->next = new ListNode(t % 10); //存贮进位的个位
                t /= 10;
            }
            return dummy->next;
    }
    };

**原题链接：**[2. 两数相加][2.]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/ca4b51e5db314ac6a8f558d4235626d6.png
[2.]: https://leetcode-cn.com/problems/add-two-numbers/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/c1eaf6bacafc4e14a923f6cc1d591a10.png