LeetCode-2-两数相加

  |   0 评论   |   0 浏览

题目描述:

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

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

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

解法:

两个链表顺序遍历,对应两个节点的值相加作为新链表的值,如果产生进位,需要加到下一位。

  • sumVal / 10 等于1就是产生了进位,为0则没有进位
  • sumVal % 10则是新节点的值
  • 构造root空节点,作为新链表的头节点(最终返回root.next节点)
  • 构造游标节点的作用 ? 为了标记处理新节点的当前位置
  • 为什么不复用root节点新建了游标节点?这样做最终返回新节点时找不到头节点

Java代码如下:

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0);
        ListNode cursor = root;
        int bit = 0;
        // 加了bit != 0 的条件是因为进位导致。如果两个链表最后一位相加产生进位,需要再建一个新节点
        while(l1 != null || l2 != null || bit != 0) {

            int l1Val = l1 != null ? l1.val : 0;
            int l2Val = l2 != null ? l2.val : 0;
            // 求和
            int sumVal = l1Val + l2Val + bit;
            bit = sumVal / 10;

            // 游标节点的下一个节点是新建的节点
            ListNode sumNode = new ListNode(sumVal % 10);
            cursor.next = sumNode;
            cursor = sumNode;

            if (l1 != null) {
                l1 = l1.next;
            }
            if(l2 != null) {
                l2 = l2.next;
            }
        }

        return root.next;
    }

运行结果:

image.png


标题:LeetCode-2-两数相加
作者:guobingwei
地址:http://guobingwei.tech/articles/2020/11/08/1604831761334.html