package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	carry := 0
	var output, co *ListNode
	c1 := l1
	c2 := l2
	for {
		if c1 != nil && c2 != nil {
			sum := c1.Val + c2.Val + carry
			carry = sum / 10
			rem := sum % 10
			c1.Val = rem
			c2.Val = rem

			if c1.Next == nil && c2.Next == nil {
				if carry > 0 {
					c1.Next = &ListNode{
						Val: 1,
					}
					carry = 0
				}
			}

			c1 = c1.Next
			c2 = c2.Next
			continue
		}

		if c1 != nil {
			output = l1
			co = c1
			break
		} else if c2 != nil {
			output = l2
			co = c2
			break
		} else {

			output = l1
			break
		}
	}

	if co != nil {
		for {
			sum := co.Val + carry
			carry = sum / 10
			rem := sum % 10

			co.Val = rem
			if co.Next == nil {
				if carry > 0 {
					co.Next = &ListNode{
						Val: 1,
					}
				}
				break
			}
			co = co.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))
}