【leetcode】单链表中的环问题

小鱼儿 2022-06-05 12:39 151阅读 0赞

### 基础版： ###

**Linked List Cycle**

判断一个单链表中是否有环？

### 拓展版： ###

**Linked List Cycle II**

如果有环，则找到环的起始位置并返回。

## 基本思路：双指针 ##

对于环的判断，网上经典的做法是：使用两个指针slow和fast，其中slow一次走一步，fast一次走两步，因为fast比slow走得快，那么如果存在环的话，二者必定会在某个位置相遇。

bool hasCycle(ListNode *head) { 
            ListNode *slow = head;
            ListNode *fast = head;
            while (fast != NULL && fast->next != NULL) { 
                slow = slow->next;
                fast = fast->next->next;
                if (slow == fast) { 
                    return true;
                }
            }
            return false;
            }

## 拓展 ##

由此，可以拓展出一些相关的问题来：

1. 环的长度是多少？
    
    2. 如何找到环中第一个节点（即Linked List Cycle II）？
    
    3. 如何将有环的链表变成单链表（解除环）？

首先可以看下面这张图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZWVubGlnaHRfNzQxMTA_size_16_color_FFFFFF_t_70]  
其中，X是起点，Y是环的交叉点，Z是快慢指针的相遇点，a、b、c表示相应的线段长度。

接下来逐个问题来分析一遍：

1.  环的长度是多少？

第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b。
    
    因为fast的速度是slow的两倍，所以fast走的距离是slow的两倍，有 2(a+b) = a+b+c+b，可以得到a=c（这个结论很重要！）。
    
    我们发现L=b+c=a+b，也就是说，从一开始到二者第一次相遇，循环的次数就等于环的长度。

1.  如何找到环中第一个节点（即Linked List Cycle II）？

我们已经得到了结论a=c，那么让两个指针分别从X和Z开始走，每次走一步，那么正好会在Y相遇！也就是环的第一个节点。

1.  如何将有环的链表变成单链表（解除环）？

在上个问题的基础上，将Y结点的next置为NULL即可。

本文思路来自于博客园：[https://www.cnblogs.com/hiddenfox/p/3408931.html][https_www.cnblogs.com_hiddenfox_p_3408931.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZWVubGlnaHRfNzQxMTA_size_16_color_FFFFFF_t_70]: /images/20220605/cafd59152aea493eb73ee028d519ee0e.png
[https_www.cnblogs.com_hiddenfox_p_3408931.html]: https://www.cnblogs.com/hiddenfox/p/3408931.html