分享
leetcode-hot-(2/100)
zhangshaos · · 1413 次点击 · · 开始浏览这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
2/100-两数相加
题目描述
image.png
分析解答
从题目描述中,联想到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+树的分裂:
后续遍历,插入节点,"计算进位",然后对父节点同样处理进位
有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信1413 次点击
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
2/100-两数相加
题目描述
image.png
分析解答
从题目描述中,联想到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+树的分裂:
后续遍历,插入节点,"计算进位",然后对父节点同样处理进位