fix/445: add other solution

novahe · novahe · commit daa7c7f0440e · 2021-08-21T00:31:31.000+08:00
diff --git a/leetcode/0445.Add-Two-Numbers-II/445. Add Two Numbers II.go b/leetcode/0445.Add-Two-Numbers-II/445. Add Two Numbers II.go
@@ -67,3 +67,72 @@ func getLength(l *ListNode) int {
 	}
 	return count
 }
+
+func addTwoNumbers1(l1 *ListNode, l2 *ListNode) *ListNode {
+	reservedL1 := reversedList(l1)
+	reservedL2 := reversedList(l2)
+
+	dummyHead := &ListNode{}
+	head := dummyHead
+	carry := 0
+	for reservedL1 != nil || reservedL2 != nil || carry > 0 {
+		val := carry
+		if reservedL1 != nil {
+			val = reservedL1.Val + val
+			reservedL1 = reservedL1.Next
+		}
+		if reservedL2 != nil {
+			val = reservedL2.Val + val
+			reservedL2 = reservedL2.Next
+		}
+		carry = val / 10
+		head.Next = &ListNode{Val: val % 10}
+		head = head.Next
+	}
+	return reversedList(dummyHead.Next)
+}
+
+func reversedList(head *ListNode) *ListNode {
+	var prev *ListNode
+	for head != nil {
+		tmp := head.Next
+		head.Next = prev
+
+		prev = head
+		head = tmp
+	}
+	return prev
+}
+
+func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
+	stack1 := pushStack(l1)
+	stack2 := pushStack(l2)
+
+	dummyHead := &ListNode{}
+	head := dummyHead
+	carry := 0
+	for len(stack1) > 0 || len(stack2) > 0 || carry > 0 {
+		val := carry
+		if len(stack1) > 0 {
+			val = val + stack1[len(stack1)-1]
+			stack1 = stack1[:len(stack1)-1]
+		}
+		if len(stack2) > 0 {
+			val = val + stack2[len(stack2)-1]
+			stack2 = stack2[:len(stack2)-1]
+		}
+		carry = val / 10
+		tmp := head.Next
+		head.Next = &ListNode{Val: val % 10, Next: tmp}
+	}
+	return dummyHead.Next
+}
+
+func pushStack(l *ListNode) []int {
+	var stack []int
+	for l != nil {
+		stack = append(stack, l.Val)
+		l = l.Next
+	}
+	return stack
+}
