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

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        // 反转链表后相加
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        // while (head1 != null){ 
        //     System.out.print(head1.val);
        //     head1 = head1.next;
        // }
        // System.out.print("\n");
        // while (head2 != null){ 
        //     System.out.print(head2.val);
        //     head2 = head2.next;
        // }
        
        // 计算每一位然后头插法
        ListNode preRes = new ListNode(-1);
        int carry = 0;
        int tmp = 0;
        while (head1 != null && head2 != null){
            tmp = head1.val + head2.val + carry;
            // 计算进位
            carry = tmp / 10;
            tmp = tmp % 10;
            ListNode p = new ListNode(tmp);
            p.next = preRes.next;
            preRes.next = p;
            head1 = head1.next;
            head2 = head2.next;
        }
        while (head1 != null){
            tmp = head1.val + carry;
            // 计算进位
            carry = tmp / 10;
            tmp = tmp % 10;
            ListNode p = new ListNode(tmp);
            
            p.next = preRes.next;
            preRes.next = p;
            head1 = head1.next;
        }

        while (head2 != null){
            tmp = head2.val + carry;
            // 计算进位
            carry = tmp / 10;
            tmp = tmp % 10;
            ListNode p = new ListNode(tmp);
            
            p.next = preRes.next;
            preRes.next = p;
            head2 = head2.next;
        }
        // 高位补1
        if (carry == 1){
            ListNode p = new ListNode(1);
            p.next = preRes.next;
            preRes.next = p;
        }

        return preRes.next;

    }
    public ListNode reverseList (ListNode head){
        ListNode nullHead = new ListNode(-1);
        ListNode p = head;
        while (p != null){
            // 头插法
            ListNode q = p.next;
            p.next = nullHead.next;
            nullHead.next = p;
            p = q;
        }  
        head = nullHead.next;
        return head;
        // while (head != null){ 
        //     System.out.print(head.val);
        //     head = head.next;
        // }
        // System.out.print("\n");
    }
}