给出两个非空的链表用来表示两个非负的整数，其中，他们格子的位数是按照逆序的方式存储的，并且他们的每个节点只能存储一位数字。如果，我们将两个数相加起来，则会返回一个新的链表来表示他们的和，您可以假设除了数字0之外，这两个数都不会以0开头。
示例：
输入（2->4->3）+(5->6->4)
输出：7->0->8
原因：342+465=807
解题思路：
1、分别遍历两个链表p与q，因为逆序的，为我们运算提供了方便，只要让Ai和Bi相加即可
2、将Ai与Bi相加然后取余数，即为新计算的个位数，然后对Ai+Bi做除10操作，得到的数作为进位(程序中我们用flag标记)，
3、然后进行p=p.next q=q.next ,程序结束条件为p q均为nil。
4、当p q均为nil时，切记不要直接返回，这里要考虑到如果此时有进位的情况，也就是我们算数学的时候比如5+5的时候，个位数为0，但是十位数为1；因此此时要判断是否flag=1，如果=1，则插入一个节点，然后才生成一个完整的链表。
下面按照这个思路上代码：
type Nums struct {
Num int
Next *Nums
}
func NewNums(src []int) *Nums {
var head, tmp *Nums
for _, v :=range src {
if head ==nil { //第一个节点头节点，也可以哨兵的写法，浪费一个节点空间，用空节点
head = &Nums{v, nil}
tmp = head
continue
}
n := &Nums{v, nil}
tmp.Next = n
tmp = n
}
return head
}
//方便打印，自己写了个println函数
func Println(head *Nums) {
for {
if head !=nil {
fmt.Printf("%d", head.Num)
head = head.Next
if head !=nil {
fmt.Printf("->")
}
continue
}
fmt.Println()
break
}
}
func LeetCode2(p, q *Nums) (*Nums, error) {
var pv int
var qv int
var flag int
var head, tmp *Nums
for p !=nil || q !=nil {
pv =0
qv =0
if p !=nil {
pv = p.Num
}
if q !=nil {
qv = q.Num
}
if head ==nil {
head = &Nums{(pv + qv + flag) %10, nil}
tmp = head
}else {
t := &Nums{(pv + qv + flag) %10, nil}
tmp.Next = t
tmp = tmp.Next
}
flag = (pv + qv + flag) /10
if p !=nil {
p = p.Next
}
if q !=nil {
q = q.Next
}
if p ==nil && q ==nil {
//todo 判断flag是否为1，如果为1，补一个节点
if flag ==1 {
t := &Nums{flag, nil}
tmp.Next = t
}
return head, nil
}
}
return nil, errors.New("list error!!!")
}
网友评论