NOTES · 学习笔记
两数相加
题目
示例 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
}