2/100-两数相加
题目描述
分析解答
从题目描述中,联想到CPU的加法器:每个链表代表一个数字,每个节点则表示一位数字。
因此,我们可以模拟CPU,也设立一个进位标志位carry
。
对于合并后的新节点,节点的值value
= 对应位置两个节点的value和
+ carry
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
// 1.for each reverse-list l1, l2:
// new node's val = l1.val + l2.val + carry(初值为0)
// carry = new carry
// 2.handle left reverse-list
var (
head, tail *ListNode
carry = 0
)
p1, p2 := l1, l2
for p1 != nil && p2 != nil {
if head == nil {
tail = new(ListNode)
head = tail
} else {
tail.Next = new(ListNode)
tail = tail.Next
}
sum := p1.Val + p2.Val + carry
tail.Val = sum % 10
carry = sum / 10
p1 = p1.Next
p2 = p2.Next
}
for p1 != nil {
tail.Next = new(ListNode)
tail = tail.Next
sum := p1.Val + carry
tail.Val = sum % 10
carry = sum / 10
p1 = p1.Next
}
for p2 != nil {
tail.Next = new(ListNode)
tail = tail.Next
sum := p2.Val + carry
tail.Val = sum % 10
carry = sum / 10
p2 = p2.Next
}
if carry != 0 {
tail.Next = new(ListNode)
tail = tail.Next
tail.Val = carry
carry = 0
}
return head
}
反思
进位的思想可以推广到其他有限容量的操作上。
例如B+树的分裂:
后续遍历,插入节点,“计算进位”,然后对父节点同样处理进位
有疑问加站长微信联系(非本文作者)