LeetCode Problem 2 - Add Two Numbers

继续第二道题目，下面是问题描述：

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

这个问题比较简单，基本上解题思路是比较清晰的。输入是两个链表，链表的元素都是单个数字（0-9），要求将两个列表的相应节点数字相加，并作为结果链表返回。

这个题咋看可以马上开始解答，但是在此之前还是有一些需要注意的地方。第一点是，题目并没有说明链表的长度，所以 A 和 B 两个链表可能不一定相同长度，那么如果一个链表更长，那么相加怎么处理呢？这里就考虑直接返回即可，相当于+0。第二点是，如果相加溢出怎么处理，其实题目的例子里面已经很清晰了，溢出会发生进位，依次向后处理。第三点是，如果最后一位发生进位呢，这点容易被遗忘，需要新增一个节点。

下面是具体的代码：

// Problem 2. Add Two Numbers
// URL: https://leetcode.com/problems/add-two-numbers/tabs/description

// ListNode defines a singly-linked list
type ListNode struct {
	Val  int
	Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	head := &ListNode{0, nil} // sentinel node
	carry := 0                // carray bit

	for tail := head; l1 != nil || l2 != nil || carry != 0; tail = tail.Next {
		sum := carry

		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}

		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}

		tail.Next, carry = &ListNode{sum % 10, nil}, sum/10
	}

	return head.Next // discard sentinel node
}

这里在链表加了一个哨兵节点，主要是为了处理方便。完整的代码参见这里，以及测试代码。