题目如下:
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 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。
