面试热题（环形链表II）

我会带着你远行 2023-10-14 14:23 33阅读 0赞

> 给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 `next` 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 `null`。
> 
> 为了表示给定链表中的环，我们使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 `pos` 是 `-1`，则在该链表中没有环。**注意，`pos` 仅仅是用于标识环的情况，并不会作为参数传递到函数中。**
> 
> ![89bb8bde1fcd9e8de859dd4d94261b6c.png][]

以前做题的时候，也是关于这种类型的题，觉得很不错，想和大家分享一波

![bd68ba23aec84cf685bea90c9465f349.jpeg][]

好，言归正传，我们来开始这道题的分析

这种类型题技巧性也是非常强的，只有出现环形这种字眼，一般都是声明两个指针，一个快、一个慢，不断走的过程中，这两个点终会相遇，就好比操场跑步（现在来设置一个情景题）：

有一点小渣和老渣去跑步，老渣可是出了名的时间管理大师，因为这，身体一直不好![3fc0d015ec544fd881b911805bb61ca0.png][]，所以老渣跑步的速度一直比小渣慢，两个同时从起点出发，最后小渣和老渣在操场中再一次相遇

![31ac2b0163074ee18655cb3673149d70.png][]

因为老渣因为某种原因，身体每况愈下，但是正因为操场是一个环状，所以两个还能再次相遇

所以我们可以先通过这个环状的特点，去找到该链表快慢指针第一次相遇的地方

ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
                if(fast==slow){
                    break;
                }
            }

我们再来研究研究怎么去找环形的入口

![a6506d46ff104257bf8a40501b2108fd.png][]

所以我们就可以写出代码：

public ListNode detectCycle(ListNode head) {
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
                if(fast==slow){
                    break;
                }
            }
            if(fast==null||fast.next==null){
                return null;
            }
            slow=head;
            while(slow!=fast){
                slow=slow.next;
                fast=fast.next;
            }
            return slow;
        }

[89bb8bde1fcd9e8de859dd4d94261b6c.png]: https://img-blog.csdnimg.cn/img_convert/89bb8bde1fcd9e8de859dd4d94261b6c.png
[bd68ba23aec84cf685bea90c9465f349.jpeg]: https://img-blog.csdnimg.cn/bd68ba23aec84cf685bea90c9465f349.jpeg
[3fc0d015ec544fd881b911805bb61ca0.png]: https://img-blog.csdnimg.cn/3fc0d015ec544fd881b911805bb61ca0.png
[31ac2b0163074ee18655cb3673149d70.png]: https://img-blog.csdnimg.cn/31ac2b0163074ee18655cb3673149d70.png
[a6506d46ff104257bf8a40501b2108fd.png]: https://img-blog.csdnimg.cn/a6506d46ff104257bf8a40501b2108fd.png