2.md

2. 两数相加

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

思路

• 标签：假节点
• 链表的数字正好是倒序，可以直接从左往右加，将结果存放在一个新的链表中。
• 要考虑到进位，使用进位变量 carry 存放进位值
• 需要使用一个假头节点 dummyHead 来链接「结果链表」，假节点相当于一个桩，栓着这根绳子（链表）
• 时间复杂度：O(n)
• 空间复杂度：O(n)，需要额外的链表来存放结果链表，长度为 N

代码

// Java
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        int carry = 0; // 用于进位，进位为 1，默认为 0
        while (l1 != null || l2 != null) { // 使用 ||，因为 l1 和 l2 可能长度不一致
            int x = (l1 == null ? 0 : l1.val); // 三元运算符避免 l1.val 报错
            int y = (l2 == null ? 0 : l2.val);
            int sum = x + y + carry; //carry 为 0 时，对结果没有影响
            carry = sum / 10; // 取整，0 或 1
            curr.next = new ListNode(sum % 10); // 取余
            curr = curr.next;
            if (l1 != null) // 不能为空，否则 l1.next 报错
                l1 = l1.next; //l1.next 可以为空
            if (l2 != null)
                l2 = l2.next; //l2.next 与 l1.next 均为空时，结束循环，避免无限循环
        }
        if (carry == 1) { // [5] + [5] -> [0, 1]
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

// JavaScript
var addTwoNumbers = function (l1, l2) {
    let dummyHead = new ListNode(0);
    let curr = dummyHead;
    let carry = 0;
    while (l1 !== null || l2 !== null) {
        let x = (l1 === null ? 0 : l1.val);
        let y = (l2 === null ? 0 : l2.val);
        let sum = x + y + carry;
        carry = parseInt(sum / 10);
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (l1 !== null)
            l1 = l1.next;
        if (l2 !== null)
            l2 = l2.next;
    }
    if (carry === 1) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
};

class Solution:  
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:  
        dummy_head = ListNode(0)  
        curr = dummy_head  
        carry = 0  
        while l1 or l2:  
            value = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry  
            curr.next = ListNode(value % 10)  
            curr = curr.next  
            carry = value // 10  
            l1 = l1.next if l1 else None  
            l2 = l2.next if l2 else None  
        if carry:  
            curr.next = ListNode(carry)  
        return dummy_head.next

画解

测试用例

输入	输出	情况
l1 = [0, 1]，l2 = [0, 1, 2]	[0, 2, 2]	长度不一致
l1 = []，l2 = [0, 1]	[0, 1]	一个为空
l1 = [9, 9]，l2 = [1]	[0, 0, 1]	进位