算法 链表相加问题

链表相加问题

```l1 = [4，2，5]
l2 = [3，8，3]

l1+l2=[8，0，8]```

解决方案 一 通过数字相加

```ListNode 1 ---> Number
+          =      Number ---------> ListNode
ListNode 2 ---> Number```
```func convertListNodetoInt(l *ListNode) (result int) {
level := 0

for {
weight := 1
for i := 0; i < level; i++ {
weight *= 10
}

result += l.Val * weight

if l.Next != nil {
l = l.Next
level++
} else {
return result
}
}
}

func convertIntToListNode(result int) *ListNode {

if result == 0 {
return &ListNode{
Val:  result,
Next: nil,
}
}

level := 1

weight := 1
for (result/weight != 0) {
weight *= 10
level++
}

//当商是0的时候，才是真正的层级。但上面的逻辑多添加了一层。所以回退一层
level --
weight /= 10

if level == 1 {
return &ListNode{
Val:  result,
Next: nil,
}
}

weight = 10
var ls []*ListNode

for i := 1; i <= level; i++ {
ls = append(ls, &ListNode{
Val:  result % weight,
Next: nil,
})

//  保留商数
result /= weight
}

for i := 0; i < len(ls)-1; i++ {
ls[i].Next = ls[i+1]
}

return ls[0]
}```

方案二 链表直接相加

```3 2 5
+ 4 5 6
-------
= 7 8 1```

```func addTwoNumbers(l1 *ListNode, l2 *ListNode) (*ListNode) {

result := &ListNode{}
curr := result
carry := 0
for (l1 != nil || l2 != nil) {
_x := 0
if l1 == nil {
_x += l2.Val
} else if l2 == nil {
_x += l1.Val
} else {
_x += l1.Val + l2.Val
}

_x += carry

carry = _x / 10

curr.Next = &ListNode{
Val: _x % 10,
}
curr = curr.Next

if l1 != nil {
l1 = l1.Next
}

if l2 != nil {
l2 = l2.Next
}
}

if carry > 0 {
curr.Next = &ListNode{
Val:  carry,
Next: nil,
}
}
return result.Next
}```