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

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){
        //反转两个链表
        head1 = reverList(head1);
        head2 = reverList(head2);

        //声明虚拟头节点
        ListNode dummy = new ListNode(-1);

        // 设置进位
        int carryBit = 0;
        
        ListNode cur = dummy;

        while(head1 != null || head2 != null) {

            int x;

            if (head1 == null) {
                x = 0;
            } else {
                x = head1.val;
            }

            int y ;

            if (head2 == null) {
                y = 0;
            } else {
                y = head2.val;
            }

            int sum = x + y + carryBit;

            carryBit = sum / 10;
            int digit = sum % 10;

            ListNode digitNode = new ListNode(digit);

            cur.next = digitNode;
            cur = cur.next;

		    // 节点不为空访问指针后移
            if(head1 != null) {
                head1 = head1.next;
            }

            if (head2 != null) {
                head2 = head2.next;
            }

        }

	    // 处理最后一个进位
        if (carryBit == 1) {
            ListNode carryBitNode = new ListNode(1);
            cur.next = carryBitNode;
        }


        return reverList(dummy.next);

    }

   /**
   * 反转链表递归写法
   */
    public ListNode reverList(ListNode node) {
        if(node != null && node.next == null) {return node;}
        ListNode newhead = reverList(node.next);
        node.next.next = node;
        node.next = null;

        return newhead;
    }
}