LeetCode | Day 2
by CUNOE, April 6, 2024
两数相加
题目描述
给你两个非空的链表,表示两个非负整数。它们每位数字都是按照逆序的方式存储,并且每个节点只能存储一位数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例
输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807
解题思路
自做
参考代码注释
// 3ms
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
// 创建一个新的链表用于存储结果
result := &ListNode{}
// 用于临时传递链表的指针
lastNode := result
// 用于替代nil的0节点
zeroNode := &ListNode{Val: 0}
// 是否进位
in := false
for {
// 两数相加
sum := l1.Val + l2.Val
// 如果有进位则加1
if in { sum++ }
// 判断是否进位, 并将进位值减去10
if sum >= 10 {
in = true
sum -= 10
} else {
in = false
}
// 将结果存入新链表
lastNode.Next = &ListNode{Val: sum}
lastNode = lastNode.Next
// 判断是否到达链表尾部
if l1.Next == nil && l2.Next == nil {
if in { lastNode.Next = &ListNode{Val: 1} }
return result.Next
} else {
// 判断链表是否为空, 为空则用0节点替代
switch {
case l1.Next == nil: l1, l2 = zeroNode, l2.Next
case l2.Next == nil: l1, l2 = l1.Next, zeroNode
default: l1, l2 = l1.Next, l2.Next
}
}
}
}
学习
官方解法相似
func addTwoNumbers(l1, l2 *ListNode) (head *ListNode) {
// 创建一个新的链表用于存储结果
var tail *ListNode
// 进位
carry := 0
// 判断任意一个链表是否为空
for l1 != nil || l2 != nil {
// 防止链表长度不一致
n1, n2 := 0, 0
if l1 != nil {
n1 = l1.Val
l1 = l1.Next
}
if l2 != nil {
n2 = l2.Val
l2 = l2.Next
}
// 两数相加
sum := n1 + n2 + carry
sum, carry = sum%10, sum/10
if head == nil {
head = &ListNode{Val: sum}
tail = head
} else {
tail.Next = &ListNode{Val: sum}
tail = tail.Next
}
}
if carry > 0 {
tail.Next = &ListNode{Val: carry}
}
return
}
总结
学习的解法与自己的解法类似,但是学习的解法没考虑到实际上进位的问题,在十位数内加减法时,进位只可能为1,所以不需要用取模和取余来解决。
通过这道题目,学习了链表的基本操作,以及链表的遍历。
明天继续刷题,加油!