題目如下:
給出兩個 非空 的鏈表用來表示兩個非負的整數。其中，它們各自的位數是按照逆序的方式存儲的，並且它們的每個節點只能存儲 一位 數字。
如果，我們將這兩個數相加起來，則會返回一個新的鏈表來表示它們的和。
您可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
解題思路
上面的題目我們做如下拆分:
鏈表首先當然是循環，判斷兩個鏈表都是nil的情況則退出循環
鏈表循環過程中處理進位的問題，設置一個臨時的進位變量，變量值是在next下加上
如果最後循環完了還有進一位的情況需要把最後的進一位的值補充到鏈表最後
最後循環鏈表生成字符串數字轉換成數字
package main
import (
"fmt"
"strconv"
)
// 首先是有一個鏈表
type Node struct {
value uint32
next *Node
}
type LinkNode struct {
head *Node
}
func main() {
link1 := &LinkNode{}
link1.AddValue(2)
link1.AddValue(4)
link1.AddValue(3)
link2 := &LinkNode{}
link2.AddValue(5)
link2.AddValue(6)
link2.AddValue(4)
fmt.Println(addTwoNum(link1.head, link2.head))
}
// 添加鏈表
func (l *LinkNode) AddValue(value uint32) {
if l.head == nil {
node := Node{value: value}
l.head = &node
return
}
item := l.head
for ; item.next != nil; item = item.next {
if item.value == value {
return
}
}
//處理最後的一個鏈表連接
if item.value == value {
return
}
node := Node{value: value}
item.next = &node
}
// 翻轉單鏈
func reserveLink(n *Node) *Node {
if n == nil || n.next == nil {
return n
}
// 這個是遞歸執行函數
new := reserveLink(n.next)
// 這裡是從頭節點開始下一個節點指向前一個節點
n.next.next = n
// 這裡是把原來的節點指向置空，相當於實現了翻轉
n.next = nil
return new
}
func addTwoNum(l1 *Node, l2 *Node) (lastNum uint32) {
tail := &LinkNode{}
item := tail.head
carry := uint32(0)
// 1.鏈表首先當然是循環，判斷兩個鏈表都是nil的情況則退出循環
for l1 != nil || l2 != nil {
n1 := uint32(0)
n2 := uint32(0)
if l1 != nil {
n1 = l1.value
l1 = l1.next
}
if l2 != nil {
n2 = l2.value
l2 = l2.next
}
// 2：鏈表循環過程中處理進位的問題，設置一個臨時的進位變量，變量值是在next下加上
sum := n1 + n2 + carry
sum, carry = sum%10, sum/10
if item == nil {
tail.head = &Node{value: sum}
item = tail.head
} else {
item.next = &Node{value: sum}
item = item.next
}
}
// 3：如果最後循環完了還有進一位的情況需要把最後的進一位的值補充到鏈表最後
if carry > 0 {
item.next = &Node{value: carry}
}
// 4：最後循環鏈表生成字符串數字轉換成數字,利用之前寫的函數先翻轉，再處理
tail.head = reserveLink(tail.head)
LastNumStr := ""
item2 := tail.head
if item2 != nil {
for ; item2.next != nil; item2 = item2.next {
LastNumStr = LastNumStr + strconv.Itoa(int(item2.value))
}
LastNumStr = LastNumStr + strconv.Itoa(int(item2.value))
}
tmp, _ := strconv.Atoi(LastNumStr)
lastNum = uint32(tmp)
return
}
時間複雜度：O(\max(m,n))O(max(m,n))，其中 m,nm,n 爲兩個鏈表的長度。我們要遍歷兩個鏈表的全部位置，而處理每個位置只需要 O(1)O(1) 的時間。
空間複雜度：O(\max(m,n))O(max(m,n))。答案鏈表的長度最多爲較長鏈表的長度 +1+1。
