使用兩個(gè)非空的鏈表用來(lái)表示兩個(gè)非負(fù)的整數(shù)降允。其中，它們各自的位數(shù)是按照逆序的方式存儲(chǔ)的右蒲，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ)一位數(shù)字。如果赶熟，我們將這兩個(gè)數(shù)相加起來(lái)瑰妄，則會(huì)返回一個(gè)新的鏈表來(lái)表示它們的和。
您可以假設(shè)除了數(shù)字 0 之外映砖，這兩個(gè)數(shù)都不會(huì)以 0 開(kāi)頭间坐。即每個(gè)數(shù)字位的值都是有效的，例如 60 不會(huì)表示為 060邑退。
解題思路：鏈表求和
這里首先想到的竹宋，是將鏈表轉(zhuǎn)換成具體的數(shù)字，相加地技，再將具體的數(shù)字轉(zhuǎn)換為鏈表蜈七，具體的實(shí)現(xiàn)如下：
type ListNode struct {
Val int
Next *ListNode
}
func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
v1 := getValue(l1)
v2 := getValue(l2)
s := v1 + v2
return makeNode(s)
}
func getValue(node *ListNode) int {
v := 0
base := 0
for {
vb := math.Pow10(base)
v += node.Val * int(vb)
base++
if node.Next == nil {
break
}
node = node.Next
}
return v
}
func makeNode(v int) *ListNode {
list := make([]int, 0)
for {
rem := v % 10
list = append(list, rem)
if v < 10 {
break
}
v = (v - rem) / 10
}
if len(list) == 0 {
return nil
}
res := &ListNode{
Val: list[0],
}
temp := res
for i := 1; i < len(list); i++ {
temp.Next = &ListNode{Val: list[i]}
temp = temp.Next
}
return res
}
在一定范圍內(nèi)，這樣的實(shí)現(xiàn)是可行的莫矗，而且在我看來(lái)飒硅，這樣實(shí)現(xiàn)最大的好處是直觀砂缩，但顯然 LeetCode 不這樣認(rèn)為！
數(shù)字直接相加走不通三娩，那么庵芭，還是直接鏈表相加吧，這里要考慮進(jìn)位的問(wèn)題雀监，代碼實(shí)現(xiàn)如下：
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
carry, head := 0, l1
for {
// 值相加再加進(jìn)位
l1.Val += l2.Val + carry
// 進(jìn)位
carry = l1.Val / 10
// 求余
l1.Val %= 10
if l2.Next == nil {
break
} else if l1.Next == nil {
// 將 l2 的鏈表階段接到 l1 上
l1.Next = l2.Next
break
}
// 執(zhí)行鏈表中的下一項(xiàng)
l1 = l1.Next
l2 = l2.Next
}
// 如果前面的進(jìn)位沒(méi)有用到
for carry != 0 {
if l1.Next == nil {
l1.Next = &ListNode{0, nil}
}
l1.Next.Val += carry
carry = l1.Next.Val / 10
l1.Next.Val %= 10
l1 = l1.Next
}
return head
}
既然鏈表可以實(shí)現(xiàn)双吆，那么直接用數(shù)組呢？
// 數(shù)組轉(zhuǎn)換為鏈表
func makeNodeByList(list []int) *ListNode {
if len(list) == 0 {
return nil
}
res := &ListNode{
Val: list[0],
}
temp := res
for i := 1; i < len(list); i++ {
temp.Next = &ListNode{Val: list[i]}
temp = temp.Next
}
return res
}
// 鏈表轉(zhuǎn)換為數(shù)組
func nodeToList(node *ListNode) []int {
r := make([]int, 0)
for {
if node == nil {
break
}
r = append(r, node.Val)
node = node.Next
}
return r
}
// 數(shù)組相加
func addTwoList(l1, l2 []int) []int {
minList := l1
maxList := l2
if len(l1) > len(l2) {
minList = l2
maxList = l1
}
r := maxList
for i := range minList {
r[i] = maxList[i] + minList[i]
}
for i, v := range r {
if v >= 10 {
r[i] -= 10
if i < len(r)-1 {
r[i+1]++
} else {
r = append(r, 1)
}
}
}
return r
}
// 這里返回結(jié)果
func addTwoNumsList(l1 *ListNode, l2 *ListNode) *ListNode {
list1 := nodeToList(l1)
list2 := nodeToList(l2)
list := addTwoList(list1, list2)
return makeNodeByList(list)
}
事實(shí)證明滔悉，雖然鏈表的空間占用率較小伊诵，但是數(shù)組的時(shí)間復(fù)雜度更低，至少 LeetCode 是這樣認(rèn)為的回官。
最后貼一張數(shù)組運(yùn)行的結(jié)果圖曹宴。
附
下一題傳送門
