【力扣高频题】002.两数相加

前面的算法文章，更新了许多 专题系列 。包括：滑动窗口、动态规划、加强堆、二叉树递归套路 等。

还没读过的小伙伴可以关注同名号，在主页中点击对应链接查看哦~

接下来的一段时间，将持续 「力扣高频题」 系列文章，想刷 力扣高频题 的小伙伴可以关注一波哦 ~

2.两数相加

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

请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入： l1 = [ 2, 4, 3 ] , l2 = [ 5, 6, 4 ]

输出： [ 7, 0, 8 ]

解释： 342 + 465 = 807

示例 2:

输入： l1 = [ 9, 9, 9, 9, 9, 9, 9 ] , l2 = [ 9, 9, 9, 9 ]

输出： [ 8, 9, 9, 9, 0, 0, 0, 1 ]

解释： 9999999 + 9999 = 10009998

思路分析

在分析正确的思路之前，我们先来看几种貌似没什么问题的解法。

解法 1 ： 哎！题目都说了，这题不是加法嘛，那直接遍历一遍两个链表，记下两个整数，做完加法再转成链表不就行了嘛？

• 有没有小伙伴是这样思考这道题目的呢？
• 这样做有什么问题呢？

经常刷题的小伙伴就能很敏锐的察觉到问题所在：整数溢出

题目中的链表如果很长的话，可能转化成整数类型之后就会有 溢出风险 ，更别说再求和了。

解法 2 ： 哎！那转成整数不行，我直接从头遍历两个链表，按位相加生成一个新链表不就行了？

• 那来思考如果 遇到进位 呢？
• 如果 遇到链表长度不一 呢？

是不是又有点小困难了…

正确思路

其实 解法 2 已经有了雏形，只需将一些特殊情况考虑清楚即可。

1. 两数相加可能会产生进位，因此需要设置一个进位标志信息ca；
2. 若两数相加产生进位，该位最终的结果应该模 10 取余；
3. 若两数相加产生进位，进位标志信息ca的值应为除 10 后的整数部分；
4. 若遇到两个链表长度不一的情况，应该让短链表高位视为 0 (高位补 0 )；
5. 两个链表最高位若产生进位了，即遍历结束后，ca > 0 ，需要新添加一个进位结点，且该值应为 ca。

代码

思考清楚以上 5 个问题之后，就不难写出代码了

public static ListNode addTwoNumbers(ListNode head1, ListNode head2) {
    // 进位信息
    int ca = 0;
    int n1 = 0;
    int n2 = 0;
    // 该位的总和
    int n = 0;
    ListNode c1 = head1;
    ListNode c2 = head2;
    ListNode node = null;
    ListNode pre = null;
    // 遍历两个链表
    while (c1 != null || c2 != null) {
        // 两链表至少一个未结束
        // 若已结束，高位补 0
        n1 = c1 != null ? c1.val : 0;
        n2 = c2 != null ? c2.val : 0;
        n = n1 + n2 + ca;
        pre = node;
        node = new ListNode(n % 10);
        node.next = pre;
        // 进位信息
        ca = n / 10;
        c1 = c1 != null ? c1.next : null;
        c2 = c2 != null ? c2.next : null;
    }
    // 最高位有进位信息
    if (ca == 1) {
        pre = node;
        node = new ListNode(1);
        node.next = pre;
    }
    // 翻转链表
    return reverseList(node);
}

// 翻转链表
public static ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode next = null;
    while (head != null) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

小思考

上面的代码需要 翻转链表，才能得到正确的输出，这样做的好处是不需要暂存最终需要输出的链表的头结点。

那如果不想最后再翻转链表，而是直接输出答案，代码又该如何书写呢？小伙们可以思考一下，在评论区探讨一下你的思路吧 ！！！（提示：需要暂存头结点哦~）

~ 点赞 ~ 关注 ~ 星标 ~ 不迷路 ~！！！

关注
回复「ACM紫书」获取 ACM 算法书籍 ~
回复「算法导论」获取 算法导论第3版 ~

在看 + 转发

让你的小伙伴们一起来学算法吧！！