【架构师训练营 1 期】第八周作业


import java.util.HashMap;
import java.util.Map;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class ListNodeDemo {

    private final Map<ListNode, Integer> temp1 = new HashMap<>();
    private final Map<ListNode, Integer> temp2 = new HashMap<>();

    // 思路：两个链表同时从头部往下查找，经过每一层时分别记录两个链表的层节点，
    // 当链表1(或链表2)的子节点首次出现在链表2(或链表1)的历史节点里时，即该节点为第一个合并节点。
    public Integer getMergeVal(ListNode l1, ListNode l2) {
        if (null == l1 && null == l2) return null;

        if (null != l1) {
            if (null != temp2.get(l1)) return l1.val;
            temp1.put(l1, 1);
        }

        if (null != l2) {
            if (null != temp1.get(l2)) return l2.val;
            temp2.put(l2, 1);
        }

        return getMergeVal(
                null != l1 ? l1.next : null,
                null != l2 ? l2.next : null);
    }

    public static void main(String[] args) {
        // 合并节点
        ListNode merge_3 = new ListNode(555, null);
        ListNode merge_2 = new ListNode(444, merge_3);
        ListNode merge_1 = new ListNode(333, merge_2);

        // 链表1
        ListNode l1_3 = new ListNode(1111, merge_1);
        ListNode l1_2 = new ListNode(111, l1_3);
        ListNode l1_1 = new ListNode(11, l1_2);
        ListNode l1 = new ListNode(1, l1_1); // 链表1头指针

        // 链表2
        ListNode l2_2 = new ListNode(222, merge_1);
        ListNode l2_1 = new ListNode(22, l2_2);
        ListNode l2 = new ListNode(2, l2_1); // 链表2头指针

        Integer result = new ListNodeDemo().getMergeVal(l1_1, l2_1);
        System.out.println("预期结果：" + merge_1.val);
        System.out.println("最终结果：" + result);
    }
}