题目描述

两个非空的链表逆序表示两个非负的整数，每个节点只存储一位数字，例如：数组567表示为7->6->5。求两数相加的和，结果返回一个新链表逆序表示。

示例：
输入：1->2->3 和 7->5->2
输出：8->7->5
原因：321+257=578

解析

考察重点：链表的遍历

从链表的第一个结点起，依次访问每个结点的next引用遍历下一个结点，直到链表结尾结点，此结点next引用为null。

注意要点：

1. 同时遍历两个链表，相对应位置的结点表示的数字相加；
2. 两个链表长短不一致时，短链表遍历完全后继续遍历长链表，直到两个链表全部遍历；
3. 两个数字加和结果可能产生进位，需要定义单独的变量保存进位值；
4. 每次计算完一个结点后挂在表示结果的新链表尾部。

技巧：

1. 访问短链表结束之后，继续遍历长链表时，短链表加数可用0代替；
2. 结果可以预先定义头节点（next引用指向链表的第一个元素，但本身并不表示链表的元素），这样每次执行的结果直接链接到新链表尾部即可。
3. 定义尾指针（指向链表的最后一个结点）方便在O(1)时间复杂度上插入新的结点

代码

public class ListNode {
    Integer val;
    ListNode next;
    ListNode(Integer x) { val = x; }
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(null);//定义头节点，元素值为null
    ListNode tail = head;//定义尾指针
    int carry = 0;//表示进位
    while(l1 != null || l2 != null){//直到两个链表都遍历完全
        int num1 = (l1 != null) ? l1.val : 0;//l1如果为null，则加数为0
        int num2 = (l2 != null) ? l2.val : 0;//l2如果为null，则加数为0
        int res = num1 + num2 + carry;//两数相加，需要同时加进位carry
        ListNode node = new ListNode(res % 10);//余数为当前结点加和的结果
        tail.next = node;//链接到尾结点之后
        tail = node;//尾引用指向新的尾结点
        carry = res / 10;//求进位值
        if(l1 != null){//不为null继续遍历
            l1 = l1.next;   
        } 
        if(l2 != null){//不为null继续遍历
            l2 = l2.next;
        }
    }
    if(carry > 0){//遍历结束，如果进位大于0，新结点保存
        ListNode node = new ListNode(carry);
        tail.next = node;
    }
    return head.next;//返回链表的第一个结点
}