两数之和

题目：给定两个表示非负整数的非空链表。链表中的数字以相反的顺序存储，并且每个节点都包含一个数字。将两个链表的数字相加，并将求得的和以链表的形式返回。

例：
输入：（2 -> 4 -> 3） + (5 -> 6 -> 4)
输出： 7 -> 0 -> 8
说明： 342 + 465 = 807

题解：

1. 链表中数字以反序存储

2. 两个链表相加存在两种可能

   1. 两个链表长度相等
   2. 其中一个链表长度大于另外一个链表

3. 若两个链表长度相等，且两个链表的最高位相加之和大于10，即有进位，应为其创建新的节点。

   例如： 50 + 61，其中最高位相加之和为11，即进位为1，返回的链表应为 1 -> 1 -> 1

题解代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        // 头结点
        ListNode head = pre;
        int carry = 0;
        // 存在三种情况，l1的长度等于l2的长度，或者一长一短，还有最后节点遍历完之后，还存在值应为其创建节点
        while (l1 != null || l2 != null || carry != 0) {
            ListNode cur = new ListNode(0);
            int sum = ((l1 == null) ? 0 : l1.val) + ((l2 == null) ? 0 : l2.val) + carry;
            cur.val = sum % 10;
            carry = sum / 10;
            pre.next = cur;
            pre = cur;

            l1 = (l1 == null) ? l1 : l1.next;
            l2 = (l2 == null) ? l2 : l2.next;
        }
        return head.next;
    }
}