[数据结构与算法]1.5 单链表相交问题

给定两个单链表，判断是否相交，返回相交节点，单链表可能有环

1. 求链表是否有环，返回入环节点

利用快慢指针计算出来是否有环，死记硬背就好

1. 快指针一次走两步，慢指针一次走一步，
   1.1 走到底 直接返回null，没有换
   1.2 或者快慢指针一样时退出
2. 如果快慢指针重合，则快指针回到头结点，快慢指针一次走一步，当再次重合时，就是入环节点

2. 有环相交，无环相交

1. 一个有环一个无环，不可能相交
2. 两个都有环
   2.1 入环前相交
   2.2 环上相交
3. 两个都无环，无环相交

无环相交计算流程

1. 如果尾部节点不一样，一定不想交
2. 如果尾部节点一样，则长的链表先走两链表的长度差
3. 然后短链表和长链表一起走，直到有相等的节点，返回

3. 代码

    /**
     * 得到入环节点
     *
     * @param head
     * @return
     */
    public Node getLoopNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Node s = head.next, f = head.next.next;
        while (s != f) {
            if (s.next == null || f.next == null || f.next.next == null) {
                return null;
            }
            s = s.next;
            f = f.next.next;
        }
        f = head;
        while (s != f) {
            s = s.next;
            f = f.next;
        }
        return f;
    }
    /**
     * 无环节点相交，或者环前相交
     *
     * @param head
     * @return
     */
    public Node getCrossNodeOfNoLoop(Node h1, Node h2, Node end) {
        if (h1 == null || h2 == null) {
            return null;
        }
        int len1 = 0, len2 = 0;
        Node c1 = h1, c2 = h2;
        while (c1.next != end) {
            len1++;
            c1 = c1.next;
        }
        while (c2.next != end) {
            len2++;
            c2 = c2.next;
        }
        // end == null 表示无环相交， end != null, 表示环前相交
        if (end == null && c1 != c2) {
            return null;
        }
        Node tall, shorted;
        if (len1 > len2) {
            tall = h1;
            shorted = h2;
        } else {
            tall = h2;
            shorted = h1;
        }
        int steps = Math.abs(len1 - len2);
        while (steps > 0) {
            steps--;
            tall = tall.next;
        }
        while (tall != null && tall != shorted) {
            tall = tall.next;
            shorted = shorted.next;
        }
        return tall;
    }
	 /**
     * 有环相交
     *
     * @param head
     * @return
     */
    public Node crossOfLoop(Node h1, Node loop1, Node h2, Node loop2) {
        // 环前相交
        if (loop1 == loop2) {
            return getCrossNodeOfNoLoop(h1, h2, loop1);
        }
        Node curr = loop1.next;
        while (curr != loop1 && curr != loop2) {
            curr = curr.next;
        }
        if (curr == loop1) {
            return null;
        }
        return loop2;
    }
     /**
     * 节点相交
     *
     * @param head
     * @return
     */
    public Node getCrossNode(Node h1, Node h2) {
        Node loop1 = getLoopNode(h1), loop2 = getLoopNode(h2);
        if (loop1 != null && loop2 != null) {
            return crossOfLoop(h1, loop1, h2, loop2);
        }
        if (loop1 == null && loop2 == null) {
            return getCrossNodeOfNoLoop(h1, h2, null);
        }
        return null;
    }
    /**
     * 两环相交比较器
     *
     * @param head
     * @return
     */
    public Node getCrossNodeCompare(Node h1, Node h2) {
        Set<Node> set1 = new HashSet<>();
        Node curr = h1;
        while (curr != null) {
            if (!set1.add(curr)) {
                break;
            }
            curr = curr.next;
        }
        Set<Node> set2 = new HashSet<>();
        curr = h2;
        while (curr != null) {
            if (set1.contains(curr)) {
                return curr;
            }
            if (!set2.add(curr)) {
                break;
            }
            curr = curr.next;
        }
        return null;
    }
    /**
     * 测试用例
     *
     * @param head
     * @return
     */
    @Test
    public void test() {
        for (int i = 0; i < 10000; i++) {
            Node[] nodes = Reduce.linkTwo(10, 100);
            Node h1 = nodes[0], h2 = nodes[1];
            Node c1 = getCrossNode(h1, h2);
            Node c2 = getCrossNodeCompare(h1, h2);
            if (c1 != c2) {
                System.out.println(Reduce.print(h1));
                System.out.println(Reduce.print(h2));
                System.out.println(c1);
                System.out.println(c2);
                return;
            }
        }
    }
    /**
     * 具体测试用例
     *
     * @param head
     * @return
     */
    @Test
    public void test2() {
        String str1 = "41->-95->-83->-21->-80->67->74->-62->-21", str2 = "67->74->-62->-21->-80->67";
        String[] arr1 = str1.split("->"), arr2 = str2.split("->");
        Map<String, Node> map = new HashMap<>();
        for (String it : arr1) {
            if (map.containsKey(it)) {
                break;
            }
            map.put(it, new Node(Integer.parseInt(it)));
        }
        for (String it : arr2) {
            if (map.containsKey(it)) {
                break;
            }
            map.put(it, new Node(Integer.parseInt(it)));
        }

        Node h1 = map.get(arr1[0]), h2 = map.get(arr2[0]);
        Node curr = h1;
        for (int i = 1; i < arr1.length && curr.next == null; i++, curr = curr.next) {
            curr.next = map.get(arr1[i]);
        }
        curr = h2;
        for (int i = 1; i < arr2.length && curr.next == null; i++, curr = curr.next) {
            curr.next = map.get(arr1[i]);
        }
        Node c1 = getCrossNode(h1, h2);
        Node c2 = getCrossNodeCompare(h1, h2);
        if (c1 != c2) {
            System.out.println(Reduce.print(h1));
            System.out.println(Reduce.print(h2));
            System.out.println(c1);
            System.out.println(c2);
            return;
        }
    }