1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
r1 := &ListNode{
Val: l1.Val,
}
r2 := &ListNode{
Val: l2.Val,
}
l1l := 0
l2l := 0
for {
if l1 != nil {
l1l += 1
r1n := r1
r1 = &ListNode{
Val: l1.Val,
Next: r1n,
}
l1 = l1.Next
}
if l2 != nil {
l2l += 1
r2n := r2
r2 = &ListNode{
Val: l2.Val,
Next: r2n,
}
l2 = l2.Next
}
if l1 == nil && l2 == nil {
break
}
}
var output, input *ListNode
if l1l > l2l {
output = r1
input = r2
} else {
output = r2
input = r2
}
carry := 0
var prev *ListNode
for {
sum := output.Val + carry
if input != nil {
sum = sum + input.Val
input = input.Next
}
carry = sum / 10
next := output.Next
output.Val = sum % 10
output.Next = prev
prev = output
if next == nil {
break
}
output = next
}
return output
}
func makeList(list []int) *ListNode {
output := &ListNode{
Val: list[0],
Next: nil,
}
current := output
for _, n := range list[1:] {
node := &ListNode{
Val: n,
}
current.Next = node
current = node
}
return output
}
func printList(node *ListNode) {
for {
if node == nil {
break
}
fmt.Print(node.Val)
node = node.Next
}
fmt.Println()
}
func main() {
// Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
// Output: [8,9,9,9,0,0,0,1]
l1 := makeList([]int{9, 9, 9, 9, 9, 9, 9})
l2 := makeList([]int{9, 9, 9, 9})
printList(l1)
printList(l2)
printList(addTwoNumbers(l1, l2))
}
|
