【LeetCode 算法】Linked List Cycle II 环形链表 II-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode 算法】Linked List Cycle II 环形链表 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Linked List Cycle II 环形链表 II

问题描述：

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

$链表中节点的数目范围是 [0, 10^4]\\ -10^5 <= Node.val <= 10^5\\ pos 为 -1 或者链表中的一个有效索引$

分析

和昨天的环形链表类似，利用哈希可以在 $O (N)$ 的时间下，找到第一个节点。

另一种就是空间为常数的快慢指针，就是昨天发的那个，它还有个比较学术的名字，Floyd判圈算法(Floyd Cycle Detection Algorithm)，它的应用场景很广泛，可以自行Bing，Google。

它的思路比较简单，如果存在环，那么先找到快慢指针在环中的相遇的点 x，然后再让2个指针分别从head，x出发，直到2者相遇，就是环的入口点。

思路很简单，但是大部分人还是不一定能AC。

为什么按照这个思路，可以找到的点一定是入口点?

讨论的前提是有环。

假设入口点是y，那么从 $h e a d$ 到达y需要 a步，从y到达2指针的相遇点x要走b步,b一定是小于n的,从x继续走c步到达入口y,所以环的大小为 $b + c$ 。
$f a s t 走的路程 = a + (k + 1) (b + c) + b$ 。 a 是无环段，b是环的入口到x的路程，而 $(k + 1) (b + c)$ 就是跑环的圈数， $k >= 0$ 。
而 $s l o w 的路程 = a + b$ ,因为fast的速度是slow的2倍，所以路程也是其2倍，即
$2*(a+b)\\ (k+1)(b+c) = a+b\\ k(b+c)+c = a$

到这里就会可以得到一个结论，设置2个指针分别从点x和head出发，每次一步，如果相遇就是入口点。

如果你无法理解这个结论.

提示你可以从路程的角度来思考，即一个从x出发的指针，它可能走c，或者是k(b+c)+c,然后恰好与另一个指针在入口相遇。

$时间复杂度 O (N)$

$空间复杂度 O (1)$

代码

哈希

public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet();
        ListNode p = head;
        while(p!=null){
            if(!set.add(p)) return p;
            p = p.next;
        }
        return null;
    }

时间复杂度 $O (N)$

空间复杂度 $O (N)$

快慢指针

public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null) return null;        
        ListNode vh = new ListNode(-1);
        vh.next = head;
        ListNode f = vh, s = vh;
        while(f!=null&&f.next!=null){ 
            f = f.next.next;
            s = s.next;
            if(f==s) break;
        } 
        if(f==null||f.next==null) return null;
        ListNode p = vh, q = f;
        while(p!=q){
            p = p.next;
            q = q.next;
        }
        return q;
    }