力扣：2. 两数相加 题解（Java）

题目地址：两数相加

 

题目描述：

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

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

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

示例：

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

 

解题思路：

1.先判断给定的两个链表那个更长，用长的链表来存储相加后的数据。不够的话再创建新节点，以减少空间的使用。

2.同时遍历两个链表，将节点中的数据取出加和，所得结果的个位存入链表中较长的那个中，所得结果的十位保留，这是进位。

3.当较短的链表遍历完后，继续遍历较长的链表，将节点中的数据取出与上一轮所得结果的十位加和，保留个位，十位用于下一轮的加和。

4.当较长的链表遍历完，但最后一轮所得结果的十位不为零，常见新的节点存储该结果的十位，并将其连接到较长链表的后面。

代码：

/**
 * 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 p1 = l1, p2 = l2, head = l1;
        int temp = 0, d1 = 0, d2 = 0;

        while(p1.next != null){
            d1++;
            p1 = p1.next;
        }
        while(p2.next != null){
            d2++;
            p2 = p2.next;
        }

        p1 = l1;
        p2 = l2;
        if(d1 < d2){
            p1 = l2;
            p2 = l1;
            head = l2;
        }
        do{
            temp += p2.val + p1.val;
            p1.val = temp % 10;
            temp /= 10;
            if(p1.next == null) break;
            p1 = p1.next;
            p2 = p2.next;
        }while(p2 != null);
        
        if(d1 != d2){
            do{
                temp += p1.val;
                p1.val = temp % 10;
                temp /= 10;
                if(p1.next == null) break;
                p1 = p1.next;
            }while(p1 != null);
        }
        ListNode tem = new ListNode(temp);
        if(temp != 0) {
            p1.next = tem;
        }
        return head;
    }
}