无环

面试题 02.07. 链表相交

哈希表

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Map<ListNode, Integer> hm = new HashMap<>();
        ListNode node1 = headA;
        ListNode node2 = headB;
        while(node1 != null){
            hm.put(node1, hm.getOrDefault(node1, 0)+1);
            //hm.put(node2, hm.getOrDefault(node1, 0)+1);
            node1 = node1.next;
        }
        while(node2 != null){
            hm.put(node2, hm.getOrDefault(node2, 0)+1);
            if (hm.get(node2) > 1){
                return node2;
            }
            node2 = node2.next;
        }
        return null;
    }
//同理这个用set应该也是更简单

双指针，真他妈的巧啊

    //根据移动举例找到相交节点
    //先这么想,给出俩个指针挨个遍历完俩个链表,一个指针从第一个链表开始遍历,另一个从第二个链表开始遍历,
    //如果一个指针遍历完一个链表,就去遍历另一链表,可以知道两个指针遍历完俩个链表的时间是一样的,因为都是遍历俩个同样的长度
    //然后跟这道题联系起来,如果俩个链表相交,俩个指针同时到达尾部的时间一样,那是不是到达相交节点的时间也一样,
    //那么只要俩个指针同时到达了一个相同的节点,是不是就算找到了相交节点了,
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A =   A != null ? A.next : headB;
            B =   B != null ? B.next : headA;
        }
        return A;
    }

有环

141. 环形链表

哈希表

    public boolean hasCycle(ListNode head) {
        Map<ListNode, Integer> hm = new HashMap<>();
        ListNode cur = head;
        while (cur!=null){
            hm.put(cur, hm.getOrDefault(cur, 0)+1);
            if ( hm.get(cur) > 1){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //hashset更简单
    public class Solution {
        public boolean hasCycle(ListNode head) {
            Set<ListNode> seen = new HashSet<ListNode>();
            while (head != null) {
                if (!seen.add(head)) {
                    return true;
                }
                head = head.next;
            }
            return false;
        }
    }

双指针

本方法需要读者对「Floyd 判圈算法」（又称龟兔赛跑算法）有所了解。

假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while( fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast)
                return true;
        }
        return false;
    }

142. 环形链表 II

在上题的基础上，不仅要判断有没有环，还要找到环的入口

当相遇时，slow指针走过的节点数为：x + y（这里slow一定是在第一圈就碰到了fast），fast走过的节点数为：x + y + n*(y + z)，fast的速度是slow的两倍，因此相遇时有等式x + y + n*(y + z) = 2*(x + y)，化简得：x = (n - 1)*(y + z) + z，说明：当两个指针分别从头结点和slow fast相遇结点出发，两者相遇的时候，即为环形入口，n-1表示在相遇前，从之前相遇点出发的结点已经走了好几圈了

    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while ( fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast){//有环
                //这里不浪费资源，不然可以用新的结点
                fast = head;
                while (slow != fast){
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
        }
        return null;
    }