2.两数相加（链表）

发表于 | 分类于 | 阅读次数

题目：

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

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

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

示例：

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

题解

测试用例分析

2+5=7；

4+6=10->记0进1，0=10%10(除10取余)，1=10/10(整除运算,除10取整)；

3+4=7->7+1(上个和运算的进位y)=8。

两位数相加，进位y为0或1（因为最大情况为：个位9+9->进1;十位9+9+1->进1）。

特殊情况考虑

  • (1)链表1和链表2的结点数不同：（2->4)+(5->6->4)
  • (2)其中一个链表为空；
  • (3)链表1和链表2的尾结点还有进位y>0：(2->4)+(5->6)=(7->0->1)

难点分析

我能算出结果链表的每个val，但是怎么链接起来？以及怎么将结果链表返回？

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 哑结点dummyHead用来链接最后的"结果链表"，初始化结点：
        ListNode dummyHead = new ListNode(0);
        // 关键点1：引用变量curr和dummyHead均指向ListNode对象[0]
        ListNode curr = dummyHead;
        int carry = 0;// 表示进位变量，为0或1
        int eachSum; //表示每组之和
        //(1)||条件能解决两链表结点数不同的情况
        while (l1 != null || l2 != null) {
            //(2)判空能解决链表为空或结点为空的情况
            int val1 = l1 == null ? 0 : l1.val;
            int val2 = l2 == null ? 0 : l2.val;
            eachSum = val1 + val2 + carry;// 加上上组计算的进位数carry
            carry = eachSum / 10;// 进位=除10取整
            //结果链表结点val=除10取余
            curr.next = new ListNode(eachSum % 10);
            //关键点2：当前节点向前移动
            curr = curr.next;
            //向下遍历结点，直至l1/l2结点均空
            l1 = l1 != null ? l1.next : null;
            l2 = l2 != null ? l2.next : null;
        }
        //(3)遍历到最后结点，还有进位，结果链表需增加结点。
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        //初始val为0的头结点不要
        return dummyHead.next;
    }
}

关键点

1、当前节点ListNode curr，在实现时需要让curr=curr.next，引用变量curr指向curr.next所指的对象,相当于curr的指针不断向前移动。

结束循环后的curr最后只是结果链表的尾结点，因此需要另一个ListNode变量来链接整个结果链表。

2、ListNode dummyHead哑结点，初始化时val可设为0，最后返回dummyHead.next即可。

3、循环前ListNode curr=dummyHead。curr与dummyHead指向同一对象(初始val为0的对象，这里称为初始对象[0])，即头结点。示例：循环(1):对象[0]的next变量指向对象[7]->curr=curr.next，变量curr指向对象[7]；循环(2)：对象
[7]的next变量指向新建对象[0],curr也指向这个对象。

因此，dummyHead能链接整个结果结点。

图解.png

图解.png

题目：力扣No.2-两数相加