2. Add Two Numbers 两数之和 链表版

1. 题目详情

• leetcode题目地址 (opens new window)
• leetcode-cn题目地址 (opens new window)

📗difficulty：Medium

🎯Tags：

• Linked List (opens new window)
• Math (opens new window)

题目描述：

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

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

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

样例：

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

2. 解题思路

题目要求已经说明，要相加的两个数，逆序方式存储在数组中，所以直接去遍历即可。但是为了更方便地处理链表，一种常见的处理方式是，new 一个新的“假”头节点 dummyHead 。返回时，返回 dummyHead.next 即可。

根据题意，一种显而易见的方式是按照数学上的竖式计算法进行计算，每次相加 l1.val + l2.val + carry，carry 为上次的进位，初始值为 0，下次 carry 的值为 carry / 10。每次需要保存下来的值，可以选择 new 一个节点存放，然后接上上个位置即可。

3. 优秀解答

3. 1 Solution1

📃帖子原址 (opens new window)

核心代码：

public class SubmitSolution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode prev = new ListNode(0);
        ListNode head = prev;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            ListNode cur = new ListNode(0);
            int sum = ((l2 == null) ? 0 : l2.val) + ((l1 == null) ? 0 : l1.val) + carry;
            cur.val = sum % 10;
            carry = sum / 10;
            prev.next = cur;
            prev = cur;
            
            l1 = (l1 == null) ? l1 : l1.next;
            l2 = (l2 == null) ? l2 : l2.next;
        }
        return head.next;
    }
}

Complexity analysis:

• Time complexity: $O(n)$.
• Space complexity: $O(n)$.
  • 在 while 循环中，每次创建了一个新的 cur 节点