链表——找到入环第一个节点（Leetcode.142）

题目：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

说明：不允许修改给定的链表。

1、笔试（额外容器）

笔试：使用额外容器——HashSet

由于单链表只有一个next指针，所以如果一个单链表在某一节点入环了，那么它就不可能再跳出这个环了
利用 HashSet 的元素唯一性，根据 next 指针指向将节点依次存入 set，当判断 set 中有重复节点的时候。即为第一个入环节点
使用hashset结构，时间复杂度O（N），额外空间复杂度O（N）

代码实现：

public class GetLoopNode {
    public static class ListNode{
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode detectCycle(ListNode head) {
        ListNode loopNode = null;

        ListNode curNode = head;
        LinkedList<ListNode> listNodes = new LinkedList<ListNode>();

        while (curNode != null){
            if (!listNodes.contains(curNode)){
                listNodes.add(curNode);
                curNode = curNode.next;
            }else {
                loopNode = curNode;
                break;
            }
        }
        return loopNode;
    }
}

2、面试（快慢指针）

面试：使用快慢指针

如果head为null，或者长度为1，或者无环，都应该返回 null；
如果存在环，快指针就会首先进入环，并不断在环内循环，且一定会在某处遇到慢指针；
相遇之时，用另外一个指针从 head 开始出发，和慢指针一起一次走一步，最终此指针和慢指针相交位置就是第一个入环节点；
关于追及问题，好像是小学奥赛题。数学推导证明：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/

代码实现：

public class GetLoopNode {
    public static class ListNode{
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

 
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null){
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;

        while (fast != null){
            slow = slow.next;
            
            //如果 fast 走向 null，说明必然无环
            if (fast.next != null){
                fast = fast.next.next;
            }else {
                return null;
            }

            //如果存在相交节点，则必然存在环，找到入环节点即可
            if (fast == slow){
                ListNode ptr = head;
                while (ptr != slow){
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }

        return null;
    }

}