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))
}