subject

Two non empty linked lists are given to represent two non negative integers. Among them, their respective digits are stored in reverse order, and each node can only store one digit.

If we add the two numbers together, we will return a new linked list to represent their sum.

You can assume that neither of these numbers starts with 0 except for the number 0.

Example:

Input: (2 - > 4 - > 3) + (5 - > 6 - > 4)
Output: 7 - > 0 - > 8
 Reason: 342 + 465 = 807

Explain

The nodes of the linked list are defined as follows

type ListNode struct {
	Val  int
	Next *ListNode
}

Answer

Pay attention to handling carry.

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	var (
		t1 *ListNode = l1
		t2 *ListNode = l2
		p  *ListNode
	)

	// For the convenience of coding, a dumb node is set up
	ret := &ListNode{
		Val:  0,
		Next: nil,
	}
	p = ret

	var (
		x     int
		y     int
		carry int = 0
		s     int = 0
	)

	for t1 != nil || t2 != nil {
		if t1 != nil {
			x = t1.Val
		} else {
			x = 0
		}
		if t2 != nil {
			y = t2.Val
		} else {
			y = 0
		}

		s = x + y + carry
		carry = s / 10

		p.Next = &ListNode{
			Val:  s % 10,
			Next: nil,
		}
		p = p.Next

		if t1 != nil {
			t1 = t1.Next
		}
		if t2 != nil {
			t2 = t2.Next
		}
	}

	if carry != 0 {
		p.Next = &ListNode{
			Val:  carry,
			Next: nil,
		}
	}

	// Remove the dumb node and return
	ret = ret.Next
	return ret
}

Function to create test data

func createTestData(a []int, b []int) (*ListNode, *ListNode) {
	const textErr = "bad param"
	if a == nil || b == nil {
		panic(textErr)
	}
	m, n := len(a), len(b)
	if m == 0 || n == 0 {
		panic(textErr)
	}
	if (a[0] == 0 && m != 1) || (b[0] == 0 && n != 1) {
		panic(textErr)
	}
	for i := 0; i < m; i++ {
		if a[i] < 0 || a[i] > 9 {
			panic(textErr)
		}
	}
	for i := 0; i < n; i++ {
		if b[i] < 0 || b[i] > 9 {
			panic(textErr)
		}
	}
	var l1 *ListNode
	var l2 *ListNode
	var p *ListNode
	var q *ListNode
	for i := 0; i < m; i++ {
		p = &ListNode{
			Val:  a[i],
			Next: nil,
		}
		if i == 0 {
			q = p
			l1 = p
		} else {
			q.Next = p
			q = p
		}
	}
	for i := 0; i < n; i++ {
		p = &ListNode{
			Val:  b[i],
			Next: nil,
		}
		if i == 0 {
			q = p
			l2 = p
		} else {
			q.Next = p
			q = p
		}
	}
	return l1, l2
}