NOTES · 学习笔记

两数相加

LeetCode链表 · 中等约 10 分钟

题目

示例 1

我们看示例 1,给了两个链表,l1 = [2,4,3],l2 = [5,6,4]。最终要输出 [7,0,8]。

因为链表是逆序存储的,所以 l1 表示 342,l2 表示 465,相加得到 807。我们需要将结果按照个位、十位、百位的顺序存入链表,也就是 [7,0,8]。

虚拟头节点与尾插法

这里引入一个虚拟头节点 (dummy),通过尾插法构建结果链表。

dummy -> nil

1. 我们将个位 7 通过插入尾部得到:dummy -> 7 -> nil

2. 我们将十位 0 通过插入尾部得到:dummy -> 7 -> 0 -> nil

3. 我们将百位 8 通过插入尾部得到:dummy -> 7 -> 0 -> 8 -> nil

就得到了题目要求的答案。

逐位相加

如何实现呢:

分别定义两个指针 p 和 q,指向链表 l1 和 l2。每次循环时,取出两个节点的值与进位 carry 相加,得到 sum,再计算当前位的数字和下一次的进位。

第一次循环:p.Val = 2,q.Val = 5,sum = 2 + 5 + carry(0) = 7,当前位数字是 7,进位是 0。

第二次循环:p.Val = 4,q.Val = 6,sum = 4 + 6 + 0 = 10,当前位数字是 0,进位是 1。

第三次循环:p.Val = 3,q.Val = 4,sum = 3 + 4 + 1 = 8,当前位数字是 8,进位是 0。

所以结果链表是 [7,0,8]。

在构建结果链表时,我们使用 curr 指针指向当前链表的尾部。每次计算出当前位的数字 digit 后,创建一个新节点,并将它连接到 curr 后面。然后让 curr 移动到新节点,继续作为尾指针,这样就能按照个位、十位、百位的顺序,通过尾插法构建结果链表。

最后返回 dummy.Next。因为 dummy 是虚拟头节点,本身不存储结果数字,真正的结果链表从它的下一个节点开始。

代码实现

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    p := l1 //定义指针p指向l1链表
    q := l2 //定义指针q指向l2链表
    carry := 0 //表示进位
    dummy := &ListNode{}
    curr := dummy
    for p != nil || q != nil || carry != 0 {
        sum := carry //表示将所有余数加起来
        if p != nil {
            sum += p.Val //我们将指针p指向的链表l1中的值全部相加起来
            p = p.Next
        }
        if q != nil {
            sum += q.Val //同理,我们将q中的值相加起来
            q = q.Next
        }
        //接下来,我们通过相加判断
        carry = sum / 10 //整除我们得到进位
        digit := sum % 10 //digit我们取模
        //我们将模用虚拟节点放进去
        curr.Next = &ListNode{Val: digit}
        curr = curr.Next //我们将digit值放入ListNode中
    }
    return dummy.Next
}