LeetCode-2-两数相加

题目

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1:

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解题思路

顺序推进+哑结点：

对于本题的测试用例，不难知道有以下三种情况：

1. 两个链表长度一致
2. 两个链表长度一长一短
3. 两个链表在相加过程中产生进位，进位需要加在下一位

特例判断，当l1为空，直接返回l2；当l2为空，直接返回l1

新增l1，l2的指针t1，t2，方便链表的遍历；新增l3哑结点和对应指针t3，用于存储相加之后的链表

相加流程：

当两个链表其中一个不为空的时候，说明还没有加完；

由于相加的过程中，链表会出现一长一短的情况，所以在其中一个链表遍历完成之后，他的next就为空了，没有val值

我们可以将后续空的链表的值默认为0，这样在相加的时候就不会对后续没有遍历完的链表产生影响

所以对于t1，t2两个链表而言，他们的当前节点值是多少，可以由如下判断：

int x = (t1!=null)?t1.val:0;
int y = (t2!=null)?t2.val:0;

之后当前的和为sum = (x+y+carry);

判断进位：进位是多少可以由sum/10得到

存储节点：每个节点只能存储1位数字，多出的部分成为进位，所以sum=sum%10，利用哑结点的后一位建立一个新的节点t3.next = new ListNode(sum);

顺序移动t1，t2，t3，其中当t1，t2为空的时候就不再需要移动了，只需要下次用0相加即可

新增进位节点：如果最后遍历完毕仍然有进位，那么尾节点就是最后以进位为值的节点t3.next = new ListNode(carry)

最后返回哑结点的next就是头节点

Java代码

/**
 * 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;
        int carry = 0;
        int sum = 0;
        ListNode t1 = l1;
        ListNode t2 = l2;
        ListNode l3 = new ListNode(0);
        ListNode t3 = l3;
        while(t1!=null||t2!=null){
            int x = (t1!=null)?t1.val:0;
            int y = (t2!=null)?t2.val:0;
            sum = (x+y+carry);
            carry = sum/10;
            sum = sum%10;
            t3.next = new ListNode(sum);
            if(t1!=null) t1 = t1.next;
            if(t2!=null) t2 = t2.next;
            t3 = t3.next;
        }
        if(carry>0) t3.next = new ListNode(carry);
        return l3.next;
    }
}