【leetcode 题目】2. 两数相加

程序员架构进阶

关注

发布于: 2021 年 04 月 01 日

原题链接

https://leetcode-cn.com/problems/add-two-numbers

题目描述

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

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

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

我的题解链接：https://leetcode-cn.com/problems/add-two-numbers/solution/lian-biao-an-wei-qiu-he-wu-xu-duo-yu-kon-9ira/

效果

执行用时：2 ms, 在所有 Java 提交中击败了 100.00%的用户内存消耗：38.7 MB, 在所有 Java 提交中击败了 76.94%的用户

解题思路

先读题，两个待加链表都是倒序存储，而且结果也是倒序，所以就比较简单，无需做链表逆序操作。我们只需要从两个链表地头结点开始，按位想加即可。需要注意的就是进位，两个数的和大于等于 10 时，需要一个临时变量记录是否进位，如果是，那么下一位的计算在两数和（也可能只有一个数，或者没有）时需要加上。边界条件：最后一次计算，只有进位，那么需要这位上补 1！！！代码如下：

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        ListNode head = new ListNode(0);        ListNode node = head;
        int add = 0;        while(l1!=null || l2!=null){            int val = 0;            if(l1!=null && l2!=null){                val = l1.val+l2.val+add;
                l1 = l1.next;                l2 = l2.next;            }else if(l1!=null){                val = l1.val+add;
                l1 = l1.next;            }else{                val = l2.val+add;                l2 = l2.next;            }
            if(val >= 10){                val = val %10;                add = 1;            }else{                add = 0;            }
            node.next = new ListNode(val);            node = node.next;        }
        if(add > 0){            node.next = new ListNode(add);        }
        return head.next;    }}

复制代码

发布于: 2021 年 04 月 01 日阅读数: 14

原文链接:【http://xie.infoq.cn/article/ac90146fcfb78398a1f56f2bf】。文章转载请联系作者。

程序员架构进阶

关注

磨炼中成长，痛苦中前行 2017.10.22 加入

微信公众号【程序员架构进阶】。多年项目实践，架构设计经验。曲折中向前，分享经验和教训

发布

暂无评论

创作场景

【leetcode 题目】2. 两数相加

原题链接

题目描述

效果

解题思路

程序员架构进阶

评论