/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	} else if l2 == nil {
		return l1
	}
	m, n := 0, 0
	for cur := l1; cur != nil; cur, m = cur.Next, m+1 {
	}
	for cur := l2; cur != nil; cur, n = cur.Next, n+1 {
	}
	var li *ListNode
	var rem int
	if m < n {
		li, rem = addRecurse(l2, l1, n, m, 0)
	} else {
		li, rem = addRecurse(l1, l2, m, n, 0)
	}
	if rem != 0 {
		li = &ListNode{rem, li}
	}
	return li
}

func addRecurse(l1, l2 *ListNode, m, n, i int) (*ListNode, int) { // n <= m
	if i == m {
		return nil, 0
	}
	a, b := l1.Val, 0
	next1, next2 := l1.Next, l2
	if m-n <= i {
		b = l2.Val
		next2 = l2.Next
	}
	li, rem := addRecurse(next1, next2, m, n, i+1)
	c := a + b + rem
	c, rem = c%10, c/10
	li = &ListNode{c, li}
	return li, rem
}