题2：类型：链表、数组

• 题目：给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
  如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
  您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
  示例：
  输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
  输出：7 -> 0 -> 8
  原因：342 + 465 = 807

• 链表相加
  1、同一循环下，为两个链表设立遍历指针，并且创建结果链表；
  2、在结果链表中，将计算结果插入尾部，十位时应注意个位的进位，以此类推；
  3、 单独处理最高进位的节点，最后返回结果链表的头节点;
  4、该题主要应用于大数相加。

注意：本题位数在链表中是逆序存储，所以从头到尾顺序依次相加正好符合运算规则；逐位向加，保存进位是关键；若最后一位进位为1，需要创建一个新的节点；判断输入的两个链表的长短，短链表无节点后取0.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 两个链表的遍历指针
        ListNode p1 = l1;
        ListNode p2 = l2;
        //创建结果链表,头节点resultHead
        ListNode resultHead = new ListNode(0);
        ListNode curr = resultHead; //结果链表遍历指针，代表当前节点
        // 进位初始值为0
        int carry = 0;
        while( p1 != null || p2 != null){
            // 获取当前节点的值，链表较短，之后无节点，取0
            int x = (p1 != null) ? p1.val : 0; 
            int y = (p2 != null) ? p2.val : 0; 

            //对应节点值相加
            int sum = x + y + carry; //第三位=第二位的进位加上对应第三位的两数
            carry = sum / 10; // 进位是下一轮用
            int num = sum % 10; // 存放新链表节点中的数值

            //将计算结果插入新链表尾部
            curr.next = new ListNode(num);
            curr = curr.next;
            // 移动节点指向下一个位置，并且判断是否为尾节点
            p1 = (p1 == null) ? p1 : p1.next;
            p2 = (p2 == null) ? p2 : p2.next;
        }
        //处理最高进位节点
        if(carry == 1){
            curr.next = new ListNode(1);
        }

        return resultHead.next;
    }
}