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

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

        // 算法的时间复杂度O(N)，额外空间复杂度O(N)

        // 1.先把两个链表都遍历到底，统计各自结点个数，并得到个位指针
        // 此外，分别创建一个HashMap记录某个结点的上一个结点
        if (head1 == null || head1.val == 0) {
            return head2;
        }
        if (head2 == null || head2.val == 0) {
            return head1;
        }
        int length1 = 1;
        int length2 = 1;
        ListNode cur1 = head1;
        ListNode cur2 = head2;
        HashMap<ListNode, ListNode> preNodeMap1 = new HashMap<>();
        HashMap<ListNode, ListNode> preNodeMap2 = new HashMap<>();
        // 预先把头结点及其前驱结点null存入HashMap
        preNodeMap1.put(head1, null);
        preNodeMap2.put(head2, null);
        while (cur1.next != null) {
            // cur1还不是最后一个结点
            length1++;
            // 存入结点cur1.next，及其前驱结点cur1
            preNodeMap1.put(cur1.next, cur1);
            cur1 = cur1.next;
        }
        while (cur2.next != null) {
            // cur2还不是最后一个结点
            length2++;
            // 存入结点cur2.next，及其前驱结点cur2
            preNodeMap2.put(cur2.next, cur2);
            cur2 = cur2.next;
        }
        // 此时，cur1和cur1指向了各自链表的最后一个非null结点

        // 2.两个链表同步往前遍历，直到各自的head
        ListNode result = null;
        int jinwei = 0;
        while (cur1 != null && cur2 != null) {
            // 3.创建result链表节点，对应结点相加，注意考虑进位，头插法
            int num1 = cur1.val;
            int num2 = cur2.val;
            int numResult = num1 + num2 + jinwei;
            int valResult = numResult % 10;
            jinwei = numResult / 10;
            // 头插法插入结果节点
            ListNode curResultNode = new ListNode(valResult);
            curResultNode.next = result;
            result = curResultNode;
            // cur1和cur2共同往前走一个结点
            cur1 = preNodeMap1.get(cur1);
            cur2 = preNodeMap2.get(cur2);
        }

        // 4.出了循环后，查看是否有一个链表没有走到头，让其无限加0即可
        // 以下两个while最多只会执行一个
        while (cur1 != null) {
            // 说明链表1没走到头，而链表2已经走到头了
            // 直接令num2 = 0
            int num1 = cur1.val;
            int num2 = 0;
            int numResult = num1 + num2 + jinwei;
            int valResult = numResult % 10;
            jinwei = numResult / 10;
            // 头插法插入结果节点
            ListNode curResultNode = new ListNode(valResult);
            curResultNode.next = result;
            result = curResultNode;
            // cur1往前走一个结点
            cur1 = preNodeMap1.get(cur1);
        }
        while (cur2 != null) {
            // 说明链表1已经走到头了，而链表2没走到头
            // 直接令num1 = 0
            int num1 = 0;
            int num2 = cur2.val;
            int numResult = num1 + num2 + jinwei;
            int valResult = numResult % 10;
            jinwei = numResult / 10;
            // 头插法插入结果节点
            ListNode curResultNode = new ListNode(valResult);
            curResultNode.next = result;
            result = curResultNode;
            // cur2往前走一个结点
            cur2 = preNodeMap2.get(cur2);
        }
        // 注意！此时jinwei中可能还有值！如果有的话，还需要再头插一个结点
        if (jinwei > 0) {
            // 头插法插入结果节点
            ListNode curResultNode = new ListNode(jinwei);
            curResultNode.next = result;
            result = curResultNode;
        }
        return result;
    }
}