牛客题解-NC3链表中环的入口节点

发表于 更新于 分类于 阅读次数：

题目

对于一个给定的链表，返回环的入口节点，如果没有环，返回null

拓展：

你能给出不利用额外空间的解法么？

思路

分析

利用快慢指针确定链表是否存在环。

是：此时的slow指针和fast指针相遇且均在环内。此时将另一个指针slow2指向链表头结点，并让slow2和slow指针同时一次移动一步。由于slow指针在环内，所以两节点一旦相遇。一定是在环的入口节点处。

否：返回null。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                ListNode slow2 = head;
                while(slow2 != slow){
                    slow2 = slow2.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}