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

思路一

• 从右到左做加法，单链表遍历可以先反转链表，变为从左到右做加法；
• 然后，反转从左到右做加法的链表，即可得到从右向左做加法的链表;

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if(head1 == null) return head2;
        if(head2 == null) return head1;

        // 反转链表
        ListNode l1 = reverse(head1);
        ListNode l2 = reverse(head2);

        // 链表相加，方向从左到右
        ListNode res = addInList2(l1, l2);

        return reverse(res);  // 反转，变成从右到左做加法
    }

    private ListNode reverse(ListNode head){  // 反转链表
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    private ListNode addInList2(ListNode head1, ListNode head2){ // 从左到右做加法
        ListNode p1 = head1, p2 = head2;
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy; // 构建新链表
        int carry = 0; // 记录进位
        while(p1 != null || p2 != null || carry > 0){
            int val = carry; // 先加上上一次的进位,可以处理链表遍历结束后，最后出现carry>0的情况
            if(p1 != null){  // 加上链表1的节点
                val += p1.val;
                p1 = p1.next;
            }
            if(p2 != null){  // 加上链表2的节点
                val += p2.val;
                p2 = p2.next;
            }
            carry = val / 10; // 进位
            val = val % 10;
            p.next = new ListNode(val); // p.next妙
            p = p.next;
        }
        return dummy.next;
    }
}