题目如下:
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
直接能够想到的就是把链表中的数组组成一个整数然后相加,但是对于较长的链表而言,整数范围是不够滴(leetcode上最后的例子数字已经超过了64位所能代表的最大整数,浮点数没有具体计算过),而且时间复杂度,应该是O(2(m+n)),取数一次操作,赋值又一次操作.所以这里考虑将每一个节点的值相加,然后赋值给新的链表,时间复杂度为O(max(m,n)),并且不会出现数值过大无法计算的情况.
代码如下
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
p1 := l1
p2 := l2
p1Next := p1
p2Next := p2
p3 := &ListNode{}
p3Next := p3
CF := 0
for {
if p1Next != nil || p2Next != nil || CF != 0{
v1 :=0
if(p1Next != nil){
v1= p1Next.Val
}
v2 := 0
if(p2Next != nil){
v2= p2Next.Val
}
val := v1 + v2 + CF
if val >= 10 {
p3Next.Val = val - 10
CF = 1
} else {
p3Next.Val = val
CF = 0
}
if p1Next != nil {
p1Next = p1Next.Next
}
if p2Next != nil {
p2Next = p2Next.Next
}
if(p1Next != nil || p2Next!= nil || CF!=0){
p3Next.Next = &ListNode{}
p3Next = p3Next.Next
}
}else{
break
}
}
return p3
}
