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

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

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


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版 ~

在看 + 转发

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

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部