Skip to content

Commit ae0f863

Browse files
gogogoobergogogoober
committed
updates to add 2 numbers
1 parent 8ceb9f4 commit ae0f863

File tree

3 files changed

+141
-84
lines changed

3 files changed

+141
-84
lines changed

‎add_two_numbers_2/solution.go

Lines changed: 132 additions & 81 deletions
Original file line numberDiff line numberDiff line change
@@ -1,103 +1,154 @@
11
package add_two_numbers_2
22

33
import (
4+
"slices"
5+
"strings"
6+
47
"github.com/austingebauer/go-leetcode/structures"
5-
"math/big"
8+
// "math/big"
9+
10+
"strconv"
611
)
712

813
func addTwoNumbers(l1 *structures.ListNode, l2 *structures.ListNode) *structures.ListNode {
9-
num1 := depthFirstNum(l1)
10-
num2 := depthFirstNum(l2)
11-
12-
var sum big.Int
13-
sum.Add(num1, num2)
14+
l1NumString := ""
15+
l2NumString := ""
1416

15-
// single digit sum
16-
if len(sum.String()) == 1 {
17-
return &structures.ListNode{
18-
Val: int(sum.Int64()),
19-
Next: nil,
17+
for true {
18+
l1NumString = strconv.Itoa(l1.Val) + l1NumString
19+
if l1.Next == nil {
20+
break
2021
}
22+
l1 = l1.Next
2123
}
2224

23-
var sumList *structures.ListNode
24-
var current *structures.ListNode
25-
26-
for sum.String() != "0" {
27-
var lastDigit big.Int
28-
lastDigit.Mod(&sum, big.NewInt(10))
29-
30-
node := &structures.ListNode{
31-
Val: int(lastDigit.Int64()),
32-
Next: nil,
25+
for true {
26+
l2NumString = strconv.Itoa(l2.Val) + l2NumString
27+
if l2.Next == nil {
28+
break
3329
}
34-
if sumList == nil {
35-
sumList = node
36-
}
37-
if current == nil {
38-
current = node
39-
} else {
40-
current.Next = node
41-
current = current.Next
42-
}
43-
44-
sum.Div(&sum, big.NewInt(10))
30+
l2 = l2.Next
4531
}
4632

47-
return sumList
48-
}
33+
num1, _ := strconv.Atoi(l1NumString)
34+
num2, _ := strconv.Atoi(l2NumString)
35+
numSum := strconv.Itoa(num1 + num2)
4936

50-
func depthFirstNum(l *structures.ListNode) *big.Int {
51-
if l == nil {
52-
return big.NewInt(0)
53-
}
37+
numSumList := strings.Split(numSum, "")
38+
slices.Reverse(numSumList)
5439

55-
v := depthFirstNum(l.Next)
56-
return v.Mul(v, big.NewInt(10)).Add(v, big.NewInt(int64(l.Val)))
40+
numLinkedList := &structures.ListNode{}
41+
numLinkedList = addNode(numLinkedList, 0, numSumList)
42+
43+
return numLinkedList
5744
}
5845

59-
func addTwoNumbers2(l1 *structures.ListNode, l2 *structures.ListNode) *structures.ListNode {
60-
carry := 0
61-
sumList := &structures.ListNode{
62-
Val: 0,
46+
func addNode(nodeList *structures.ListNode, index int, numList []string) *structures.ListNode {
47+
currentValue, _ := strconv.Atoi(numList[index])
48+
nodeList = &structures.ListNode{
49+
Val: currentValue,
6350
Next: nil,
6451
}
65-
frontSumList := sumList
66-
67-
for l1 != nil || l2 != nil {
68-
// calculate sum and carry values
69-
l1Val := 0
70-
l2Val := 0
71-
if l1 != nil {
72-
l1Val = l1.Val
73-
l1 = l1.Next
74-
}
75-
if l2 != nil {
76-
l2Val = l2.Val
77-
l2 = l2.Next
78-
}
79-
80-
sum := l1Val + l2Val + carry
81-
carry = sum / 10
82-
sumList.Val = sum % 10
83-
84-
// no more list to process, but carry is not 0
85-
if l1 == nil && l2 == nil && carry > 0 {
86-
sumList.Next = &structures.ListNode{
87-
Val: carry,
88-
Next: nil,
89-
}
90-
}
91-
92-
// one or both lists still can be processed
93-
if l1 != nil || l2 != nil {
94-
sumList.Next = &structures.ListNode{
95-
Val: 0,
96-
Next: nil,
97-
}
98-
sumList = sumList.Next
99-
}
52+
if index < len(numList)-1 {
53+
index++
54+
nodeList.Next = addNode(nodeList, index, numList)
10055
}
101-
102-
return frontSumList
56+
return nodeList
10357
}
58+
59+
// func addTwoNumbers(l1 *structures.ListNode, l2 *structures.ListNode) *structures.ListNode {
60+
// num1 := depthFirstNum(l1)
61+
// num2 := depthFirstNum(l2)
62+
63+
// var sum big.Int
64+
// sum.Add(num1, num2)
65+
66+
// // single digit sum
67+
// if len(sum.String()) == 1 {
68+
// return &structures.ListNode{
69+
// Val: int(sum.Int64()),
70+
// Next: nil,
71+
// }
72+
// }
73+
74+
// var sumList *structures.ListNode
75+
// var current *structures.ListNode
76+
77+
// for sum.String() != "0" {
78+
// var lastDigit big.Int
79+
// lastDigit.Mod(&sum, big.NewInt(10))
80+
81+
// node := &structures.ListNode{
82+
// Val: int(lastDigit.Int64()),
83+
// Next: nil,
84+
// }
85+
// if sumList == nil {
86+
// sumList = node
87+
// }
88+
// if current == nil {
89+
// current = node
90+
// } else {
91+
// current.Next = node
92+
// current = current.Next
93+
// }
94+
95+
// sum.Div(&sum, big.NewInt(10))
96+
// }
97+
98+
// return sumList
99+
// }
100+
101+
// func depthFirstNum(l *structures.ListNode) *big.Int {
102+
// if l == nil {
103+
// return big.NewInt(0)
104+
// }
105+
106+
// v := depthFirstNum(l.Next)
107+
// return v.Mul(v, big.NewInt(10)).Add(v, big.NewInt(int64(l.Val)))
108+
// }
109+
110+
// func addTwoNumbers2(l1 *structures.ListNode, l2 *structures.ListNode) *structures.ListNode {
111+
// carry := 0
112+
// sumList := &structures.ListNode{
113+
// Val: 0,
114+
// Next: nil,
115+
// }
116+
// frontSumList := sumList
117+
118+
// for l1 != nil || l2 != nil {
119+
// // calculate sum and carry values
120+
// l1Val := 0
121+
// l2Val := 0
122+
// if l1 != nil {
123+
// l1Val = l1.Val
124+
// l1 = l1.Next
125+
// }
126+
// if l2 != nil {
127+
// l2Val = l2.Val
128+
// l2 = l2.Next
129+
// }
130+
131+
// sum := l1Val + l2Val + carry
132+
// carry = sum / 10
133+
// sumList.Val = sum % 10
134+
135+
// // no more list to process, but carry is not 0
136+
// if l1 == nil && l2 == nil && carry > 0 {
137+
// sumList.Next = &structures.ListNode{
138+
// Val: carry,
139+
// Next: nil,
140+
// }
141+
// }
142+
143+
// // one or both lists still can be processed
144+
// if l1 != nil || l2 != nil {
145+
// sumList.Next = &structures.ListNode{
146+
// Val: 0,
147+
// Next: nil,
148+
// }
149+
// sumList = sumList.Next
150+
// }
151+
// }
152+
153+
// return frontSumList
154+
// }

‎add_two_numbers_2/solution_test.go

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,10 @@
11
package add_two_numbers_2
22

33
import (
4+
"testing"
5+
46
"github.com/austingebauer/go-leetcode/structures"
57
"github.com/stretchr/testify/assert"
6-
"testing"
78
)
89

910
func Test_addTwoNumbers(t *testing.T) {
@@ -96,7 +97,6 @@ func Test_addTwoNumbers(t *testing.T) {
9697
for _, tt := range tests {
9798
t.Run(tt.name, func(t *testing.T) {
9899
assert.Equal(t, tt.want, addTwoNumbers(tt.args.l1, tt.args.l2))
99-
assert.Equal(t, tt.want, addTwoNumbers2(tt.args.l1, tt.args.l2))
100100
})
101101
}
102102
}

‎go.mod

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,11 @@
11
module github.com/austingebauer/go-leetcode
22

3-
go 1.14
3+
go 1.18
44

55
require github.com/stretchr/testify v1.5.1
6+
7+
require (
8+
github.com/davecgh/go-spew v1.1.0 // indirect
9+
github.com/pmezard/go-difflib v1.0.0 // indirect
10+
gopkg.in/yaml.v2 v2.2.2 // indirect
11+
)

0 commit comments

Comments
 (0)