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

基本思路

两个数相加需要从后往前相加再进位，但是单向链表很难从后往前相加，因此可以将两个链表反转后从前往后相加，就相当于反转前从后往前相加，遍历时遇到空指针时则将该节点记录为0，这样保证较长的链表没遍历完时还可以处理加法逻辑，如果两个链表都记录完后，还有进位，就还需要创建节点存储进位。

结果链表采用头插法的方式，在插入的时候就是逆序的了。

参考

参考题解

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类
     */
    private ListNode reverse(ListNode head) {
        ListNode current = head;
        ListNode pre = null;
        ListNode temp = null;

        while (current != null) {
            temp = current.next;
            current.next = pre;
            pre = current;
            current = temp;
        }

        return pre;
    }
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        // 一个链表为空即全为0，返回另外一个链表
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }

        // 反转两个链表，实现从后往前的节点相加
        head1 = reverse(head1);
        head2 = reverse(head2);

        ListNode res = new ListNode(-1);
        ListNode current = null;
        int carry = 0;  // 存放进位
        int val1 = 0;  // 存放链表一的节点值
        int val2 = 0;  // 存放链表二的节点值
        int temp = 0;  // 存放两个节点值相加的结果
        res.next = current;

        while (head1 != null || head2 != null || carry != 0) {  // 当两个链表都为空时，carry不为0，还需要创建一个节点存放carry
            if (head1 != null) {
                val1 = head1.val;
                head1 = head1.next;
            }
            else {
                val1 = 0;
            }
            if (head2 != null) {
                val2 = head2.val;
                head2 = head2.next;
            }
            else {
                val2 = 0;
            }

            temp = val1 + val2 + carry;
            carry = temp/10;  // 超过10进位
            temp %= 10;

		    // 头插法存放结果
            ListNode node = new ListNode(temp);
            node.next = current;
            current = node;
            res.next = current;
        }

        return res.next;
    }
}