本文共 3582 字，大约阅读时间需要 11 分钟。

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Notice that you should not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1Output: tail connects to node index 1Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0Output: tail connects to node index 0Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1Output: no cycleExplanation: There is no cycle in the linked list.

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

题意：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 不允许修改给定的链表。最好能够使用 O(1) 空间解决此题。

解法1 哈希集合

使用哈希集合记录之前的指针，然后直接遍历即可。C++代码如下：

class Solution {
   public:    ListNode *detectCycle(ListNode *head) {
           unordered_set
   
     st;        for (ListNode *p = head; p; p = p->next) {
               if (st.find(p) != st.end()) return p;            st.insert(p);        }        return nullptr;    }};
   

对应的执行效率如下：

执行用时：20 ms, 在所有 C++ 提交中击败了25.36% 的用户内存消耗：9.6 MB, 在所有 C++ 提交中击败了21.10% 的用户

Java代码如下：

public class Solution {
       public ListNode detectCycle(ListNode head) {
           Set
   
     st = new HashSet<>();        ListNode p = head;        while (p != null) {
               if (st.add(p) == false) return p; //st中存在p则返回false; 否则添加p            p = p.next;        }        return null;    }}
   

解法2 利用堆空间特性

堆的地址从低到高，而LeetCode中的链表结点内存是顺序申请的。如果有环，则 head->next 的地址一定小于等于 head 的地址，此时返回 head->next 。

注意，这种做法不一定正确——因为堆中的内存反复 new 和 delete 之后，之前分配的地址不一定比新分配的地址小。当然，Leetcode上的内存是充足的，没有复杂的手动内存管理，它逐用例依次测试，每个测试中顺序申请链表结点，测试完一个用例之后整体删除。因此，这种做法才能通过测试：

class Solution {
   public:    ListNode *detectCycle(ListNode *head) {
           while (head) {
               if (!less
   
    ()(head, head->next)) //head的地址>=head->next                return head->next;            head = head->next;        }        return nullptr;    }};
   

提交后执行效率如下：

执行用时：12 ms, 在所有 C++ 提交中击败了65.98% 的用户内存消耗：7.9 MB, 在所有 C++ 提交中击败了28.98% 的用户

解法3 快慢指针

这种做法分为两个步骤：

• 首先通过快慢指针的方法，判断链表是否有环：lo = hi = fast ，快指针 hi 每次走两步，慢指针 lo 每次走一步，这样快指针走的路径长度始终是慢指针的两倍。若是不存在环，直接返回 null ；若存在环，则快慢指针肯定会在若干步之后相遇；
• 如果有环，则设链表起点到入环的第一个节点 A 的长度为 a (未知)，到快慢指针相遇的结点 B 的长度为 a + b (这个长度已知)，现在想知道 a 的值。注意，快指针 hi 始终是慢指针 lo 走过长度的两倍，所以慢指针 lo 从 B 继续往前走 a + b 步就又能回到 B 点，从 B 只走 a 步则会回到结点 A 。
• 当然，我们不知道 a 具体是多少步。这里的解决思路是再用一个指向起点的指针 p ，从起点到 A 的长度也是 a 步，因此 p 和 lo 同时前进，相遇之时必然是入环的第一个结点 A。

class Solution {
   public:    ListNode *detectCycle(ListNode *head) {
           if (head == nullptr) return head;        ListNode *lo = head, *hi = head;        bool hasCycle = false; //使用快慢指针判断是否有环        while (hi && hi->next) {
               hi = hi->next->next;            lo = lo->next;            if (lo == hi) {
    hasCycle = true; break; }        }        if (hasCycle) {
    //如果有环,找到入环开始的结点            ListNode *p = head;            while (p != lo) {
    //lo == hi                lo = lo->next;                p = p->next;            }            return p;         }         return nullptr;    }};

这一C++代码的执行效率是：

执行用时：4 ms, 在所有 C++ 提交中击败了99.85% 的用户内存消耗：7.9 MB, 在所有 C++ 提交中击败了28.55% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/110139454 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！