题解 | #链表相加(二)#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

// public class Solution {  // 这个方法受限于int类型的大小
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      *
//      * @param head1 ListNode类
//      * @param head2 ListNode类
//      * @return ListNode类
//      */
//     public ListNode ReverseList(ListNode head) {
//         if (head == null ||
//                 head.next == null) { //判断链表为空或长度为1的情况
//             return head;
//         }

//         ListNode pre = null;
//         ListNode cur = head;
//         ListNode tmp = null; //记录当前节点的下个节点


//         while (cur != null) {
//             tmp = cur.next;  //记录当前节点的下一个节点
//             cur.next = pre;  //让当前节点的next指向前一个节点
//             pre = cur;       //pre往前移动一位
//             cur = tmp;       //当前节点往后移动一位
//         }
//         return pre;
//     }

//     public ListNode addInList (ListNode head1, ListNode head2) {
//         // write code here
//         head1 = ReverseList(head1);
//         head2 = ReverseList(head2);
//         ListNode dummyNode = new ListNode(-1);
//         ListNode cur;
//         ListNode newhead;
//         cur = dummyNode;
//         int sum = 0;
//         int power = 1;
//         int num1, num2;
//         num1 = 0;
//         num2 = 0;
//         while (head1 != null) {
//             num1 = num1 + head1.val * power;
//             head1 = head1.next;
//             power = power * 10;
//         }
//         power = 1;
//         while (head2 != null) {
//             num2 = num2 + head2.val * power;
//             head2 = head2.next;
//             power = power * 10;
//         }
//         sum = num1 + num2;
//         while(sum!=0){
//             ListNode newNode = new ListNode(sum%10);
//             cur.next = newNode;
//             cur = cur.next;
//             sum = sum/10;
//         }

//         newhead = ReverseList(dummyNode.next);

//         return newhead;
//     }
// }

public class Solution {  // 使用进位法，不受int类型的大小限制

    public ListNode ReverseList(ListNode head) {
        if (head == null ||
                head.next == null) { //判断链表为空或长度为1的情况
            return head;
        }

        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null; //记录当前节点的下个节点


        while (cur != null) {
            tmp = cur.next;  //记录当前节点的下一个节点
            cur.next = pre;  //让当前节点的next指向前一个节点
            pre = cur;       //pre往前移动一位
            cur = tmp;       //当前节点往后移动一位
        }
        return pre;
    }

    public ListNode addInList (ListNode head1, ListNode head2){
        head1 = ReverseList(head1);
        head2 = ReverseList(head2);

        ListNode dummyNode = new ListNode(-1);
        ListNode cur=dummyNode;
        ListNode newNode;
        int carry=0;
        int tmp=0;
        
        while(head1!=null||head2!=null||carry==1){
            if(head1==null&&head2!=null){
                tmp = head2.val + carry;
                head2 = head2.next;
            } else if(head2==null&&head1!=null){
                tmp = head1.val + carry;
                head1 = head1.next;
            } else if(head1==null&&head2==null){
                tmp = carry;
            } else {
                tmp = head1.val + head2.val + carry;
                head1 = head1.next;
                head2 = head2.next;
            }
            if(tmp>10){
                newNode = new ListNode(tmp-10);
                carry = 1;
            } else if(tmp<10){
                newNode = new ListNode(tmp);
                carry = 0;
            } else {
                newNode = new ListNode(0);
                carry = 1;
            }
            System.out.println(tmp);
            cur.next = newNode;
            cur = newNode;
        }
        dummyNode.next = ReverseList(dummyNode.next);
        return dummyNode.next;
    }
}

第一种方法使用int类型存sum，但是这样的计算结果会受制于int类型的大小限制。

使用逐位求和的方法进行计算（需要反转链表），可以不受int类型限制。