题目

给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果。

• 示例：
  输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
  输出：2 -> 1 -> 9，即912
• 示例：
  输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
  输出：9 -> 1 -> 2，即912

题解

  看完题目我们首先可能会想到将链表反转生成数字，然后将两数相加，最后输出链表。这样的操作只能在int范围内使用。如果链表长度过长就会溢出。那我们可以采用什么方法让它能运行在anywhere中呢？
  看下图，我们可以将两个链表逐个相加，使用一个进位数来保存节点相加的进位，参与后面节点的相加。相加的各位就保存在新的链表中，这样无论多长的链表都能相加。

• 代码实现：

/** * 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) {
   
        if(l1 == null){
   
            return l2;
        }
        if(l2 == null){
   
            return l1;
        }
        //申明一个新的链表头节点
        ListNode head = new ListNode(-1);
        //用于参与后面的节点相加
        ListNode prev = head;
        //保存进位数
        int carry = 0;
        while(l1!=null&&l2!=null){
   
            int sum = l1.val + l2.val + carry;
            carry = sum/10;
            prev.next = new ListNode(sum%10);
            prev = prev.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        while(l1!=null){
   
            int sum = l1.val + carry;
            carry = sum/10;
            prev.next = new ListNode(sum%10);
            prev = prev.next;
            l1 = l1.next;
        }
        while(l2!=null){
   
            int sum = l2.val + carry;
            carry = sum/10;
            prev.next = new ListNode(sum%10);
            prev = prev.next;
            l2 = l2.next;
        }
        //当所有节点相加完后，进位仍有值，则追加到链表后面
        if(carry!=0){
   
            prev.next = new ListNode(carry);
        }
        return head.next;
    }
}