本文目录#

题目描述#

  • 两数相加：
    • 给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
    • 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
    • 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
  • 示例：
    • 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    • 输出：7 -> 0 -> 8
    • 原因：342 + 465 = 807

题外话#

  • 上来审题不清楚以为是倒序相加然后进位
    例如：
    • 输入（2 -> 3 -> 4) + (5 -> 6-> 7) 时，结果应该是 234 + 567 = 801，输出 8 -> 0 -> 1;
    • 这样的话咋一看其实也很简单，只需要将两个链表中的数字234和567取出后再放入链表输出即可；
    • but！！！
      • 将题解放上LeetCode后，官方的测试用例中有类似（9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9) + (5 -> 6-> 7)的极限测试，将取出的234和567相加时会抛出整数溢出异常，用BigDicimal也无解，况且实际情况中无法知道该数会有多大，放弃。

解#

  • 按题目意思输入（2 -> 3 -> 4) + (5 -> 6-> 7) 时，其实应该是 432 + 765 = 1197 ，输出 7 -> 9 -> 1 -> 1;
  • 这样的话其实只需要将每位相加，如果有进位，再加上进位后的1即可。
  • 直接贴官方的解题思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode result = dummyHead;
    int carry = 0;
    while (l1 != null || l2 != null) {
        int l1Val = (l1 != null) ? l1.val : 0;
        int l2Val = (l2 != null) ? l2.val : 0;
        int sum = l1Val + l2Val + carry;
        carry = sum / 10;
        result.next = new ListNode(sum % 10);
        result = result.next;
        if (l1 != null) {
            l1 = l1.next != null ? l1.next : null;
        }
        if (l2 != null) {
            l2 = l2.next != null ? l2.next : null;
        }
    }
    if (carry > 0) {
        result.next = new ListNode(carry);
    }
    return dummyHead.next;
}

哑结点#

  • 这题的精髓就在与哑结点的设置，可以在最后直接将链表头返回；
    • ListNode result = dummyHead;将dummyHead和result指向同一个引用；
    • 随后的result = result.next;只是在该引用后添加新的节点；
    • 最终return dummyHead.next;返回的是有效的第一个节点；

本作品系原创，采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可，转载请注明出处。