两数相加

算法思路

疑问 ： 怎么不直接按照数组遍历，搞的这么麻烦

不是“故意搞麻烦”，而是因为输入输出格式就是链表，直接操作链表就是最自然、最高效的做法。

链表遍历和数组遍历思维模型一样，只是写法略有不同（指针 vs 下标）。

如果换成数组，你需要多做“转换”这一无意义的步骤，反而更麻烦。

LeetCode 2：两条链表表示逆序的非负整数（个位在头），求和并返回同样形式的链表。

模拟竖式加法，用 carry 记录进位：

1. 同时遍历 l1、l2，直到两者都空且 carry == 0
2. 当前位和 = carry +（l1 有则加其值并后移）+（l2 有则加其值并后移）
3. 新节点值为 sum % 10，carry = sum // 10，接到结果链表尾部
4. 用哑节点 dummy 简化头指针处理，最后返回 dummy.next

时间 O(max(m, n))，空间 O(1)（不计结果链表）。

python

from typing import Optional


class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
        self.val = val
        self.next = next


def add_two_numbers(
    l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
    dummy = ListNode()
    cur = dummy
    carry = 0

    while l1 or l2 or carry:
        s = carry 
        if l1:
            s += l1.val
            l1 = l1.next
        if l2:
            s += l2.val
            l2 = l2.next
        carry, digit = divmod(s, 10)
        cur.next = ListNode(digit)
        cur = cur.next

    return dummy.next

js

function ListNode(val = 0, next = null) {
    this.val = val;
    this.next = next;
}

/**
 * @param {ListNode|null} l1
 * @param {ListNode|null} l2
 * @return {ListNode|null}
 */
function addTwoNumbers(l1, l2) {
    const dummy = new ListNode();   // 虚拟头结点，方便处理结果链表的头部
    let cur = dummy;                // cur 指向结果链表的当前末尾
    let carry = 0;                  // 进位，初始为 0

    while (l1 || l2 || carry) {     // 只要还有数未加完，或者还有进位就继续
        let sum = carry;            // 先加上上一位的进位

        if (l1) {
            sum += l1.val;          // 加上 l1 当前位的值
            l1 = l1.next;           // l1 指针后移
        }
        if (l2) {
            sum += l2.val;          // 加上 l2 当前位的值
            l2 = l2.next;           // l2 指针后移
        }

        carry = Math.floor(sum / 10); // 计算新的进位（向高位的进位）
        cur.next = new ListNode(sum % 10); // 当前位保留个位数，创建新节点
        cur = cur.next;                // 移动结果链表指针
    }

    return dummy.next;                 // 跳过虚拟头结点，返回真正的和链表头
}

go

type ListNode struct {
	Val  int
	Next *ListNode
}

func addTwoNumbers(l1, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	carry := 0

	for l1 != nil || l2 != nil || carry != 0 {
		sum := carry
		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}
		carry = sum / 10
		cur.Next = &ListNode{Val: sum % 10}
		cur = cur.Next
	}

	return dummy.Next
}