package main

/* type ListNode struct {
	Val  int
	Next *ListNode
}
*/

/* func list2str(head *ListNode) string {
	curr := head
	str := make([]rune, 0)
	for curr != nil {
		str = append(str, rune(curr.Val+'0'))
		curr = curr.Next
	}
	return string(str)
}
*/
func list2int(head *ListNode) int64 {
	beg := head
	res := int64(0)
	for i := 1; beg != nil; i *= 10 {
		res += int64(beg.Val * i)
		beg = beg.Next
	}
	return res
}

func int2list(num int64) *ListNode {
	head := &ListNode{int(num % 10), nil}
	num /= 10
	for tail := head; num != 0; num /= 10 {
		tail.Next = &ListNode{int(num % 10), nil}
		tail = tail.Next
	}
	return head
}

// will overflow
func addTwoNumbersOld(l1 *ListNode, l2 *ListNode) *ListNode {
	return int2list(list2int(l1) + list2int(l2))
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// (3->2->1) + (2->1) = (5->3->1), 123 + 12 = 135
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	// get head of result list
	head := &ListNode{(l1.Val + l2.Val) % 10, nil}
	remain := int((l1.Val + l2.Val) / 10)
	curr := head
	l1 = l1.Next
	l2 = l2.Next
	// while l1 != [] and l2 != [], calculate l1 + l2
	for l1 != nil && l2 != nil {
		curr.Next = &ListNode{(l1.Val + l2.Val + remain) % 10, nil}
		remain = int((l1.Val + l2.Val + remain) / 10)
		curr = curr.Next
		l1 = l1.Next
		l2 = l2.Next
	}
	// l1 / l2 is nil (l1 == nil, l2 == nil, do nothing)
	if l1 != nil {
		curr.Next = &ListNode{(l1.Val + remain) % 10, l1.Next}
		remain = int((l1.Val + remain) / 10)
		curr = curr.Next
	} else if l2 != nil {
		curr.Next = &ListNode{(l2.Val + remain) % 10, l2.Next}
		remain = int((l2.Val + remain) / 10)
		curr = curr.Next
	}
	// add remainder
	for remain != 0 {
		if curr.Next != nil {
			curr.Next.Val += remain
			remain = int(curr.Next.Val / 10)
			curr.Next.Val %= 10
			curr = curr.Next
		} else {
			curr.Next = &ListNode{remain, nil}
			remain = 0
		}
	}
	return head
}

/* func main() {
	l13 := ListNode{3, nil}
	l12 := ListNode{2, &l13}
	l1 := &ListNode{1, &l12}
	l23 := ListNode{9, nil}
	l22 := ListNode{9, &l23}
	l2 := &ListNode{1, &l22}
	fmt.Println(list2str(addTwoNumbers(l1, l2)))
} */