之前我的写文章《链表在STM32中的应用》


    不论在面试或者刷题过程中，很大概率都会遇到环形链表这种类型的题目，例如 leetcode 141. 环形链表 以及 leetcode 142. 环形链表 II 等，本文主要介绍通过快慢指针法来解决此类题型，以供大家参考。


环形链表
环形链表大致样子如下图所示：



快慢指针法
判断链表是否是环形链表，一般通过快慢指针法。


操作步骤
一、分别定义两个均指向头节点的指针（fast/slow）；
二、快指针每次走两步，慢指针每次走一步；
三、如果链表存在环，则快慢指针一定会在环中相遇。


     如下图示，快慢指针行走的轨迹如下：
faster：1--->3--->5--->7
slower：1--->2--->3--->4

faster：7--->5
slower：4--->5
当他们同时到达节点 5 时，完美相遇。



举栗1：判断链表是否有环

题目

Show me the Code

1. <font face="微软雅黑" size="3">//  C 语言
   
2. bool hasCycle(struct ListNode *head) {
   
3.     /* 特判 */
   
4.     if (head == NULL || head->next == NULL) {
   
5.         return false;
   
6.     }
   
7.     struct ListNode *slow = head, *fast = head;
   
8.     /* fast指针走过链表末端，说明链表无环*/
   
9.     while((fast != NULL) && (fast->next != NULL)) {
   
10.         slow = slow->next;
    
11.         fast = fast->next->next;
    
12.         if(slow == fast) {
    
13.             return true;
    
14.         }
    
15.     }
    
16.     return false;
    
17. }</font>

复制代码

1. <font face="微软雅黑" size="3"># python3
   
2. class Solution:
   
3.     def hasCycle(self, head: ListNode) -> bool:
   
4.         if not head or not head.next: return False     
   
5.         slow, fast = head, head
   
6.         while fast and fast.next:
   
7.             slow = slow.next
   
8.             fast = fast.next.next
   
9.             if slow is fast: return True
   
10.         return False  </font>

复制代码

举例2：求入环的第一个节点

题目

思路
本题除了需要判断链表是否有环外，如果有环还要求入环的第一个节点，因此是上一个题目的升级版本，还是以快慢指针中举例的那个链表作为示例，下图将描述当链表有环的时候，如何求出入环的第一个节点，见下图示：
已判断链表有环

求入环的第一个节点
让慢指针重新指向链表的头节点，并让快慢指针同时每次只走一步
faster：5--->6--->7
slower：1--->2--->3

继续走
faster：7--->4
slower：3--->4
当他们同时到达节点 4 时，再次完美相遇。





因此，由上面的图可知，当判断链表有环（快慢指针相遇）之后，再让快（或者慢）指针重新指向链表头节点，另外一个指针仍保持指向不变，然后让快/慢指针同时走，且每次只走一步，当他们再次相遇时，此时相遇的节点就是入环的第一个节点。


Show me the Code

1. <font face="微软雅黑" size="3">//  c 语言
   
2. struct ListNode *detectCycle(struct ListNode *head) {
   
3.     /* 记录是否有环 */
   
4.     bool flag = false;  
   
5.     struct ListNode *slow = head, *fast = head;
   
6.     while (fast != NULL && fast->next != NULL) {
   
7.         slow = slow->next;
   
8.         fast = fast->next->next;
   
9.         /* 有环则更新 flag 的值，并跳出循环寻找入环第一个节点 */
   
10.         if (slow == fast) {
    
11.             flag = true;
    
12.             break;
    
13.         }
    
14.     }
    
15.     /* 无环则直接返回空 */
    
16.     if (flag == false) {
    
17.         return NULL;
    
18.     }
    
19.     /* 慢指针重新指向链表头节点，快指针仍指向相遇节点 */
    
20.     slow = head;
    
21.     /* 快慢指针每次走一步，相遇节点即为入环第一个节点 */
    
22.     while (fast != slow) {
    
23.         fast = fast->next;
    
24.         slow = slow->next;
    
25.     }
    
26.     return slow;
    
27. }</font>

复制代码

1. <font face="微软雅黑" size="3">//  go 语言
   
2. 
   
3. func detectCycle(head *ListNode) *ListNode {
   
4.     slow, fast := head, head
   
5.     for fast != nil && fast.Next != nil {
   
6.         fast, slow = fast.Next.Next, slow.Next
   
7.         if fast == slow {
   
8.             break
   
9.         }
   
10.     }
    
11.     if fast == nil || fast.Next == nil {
    
12.         return nil
    
13.     }
    
14.     slow = head
    
15.     for fast != slow {
    
16.         fast, slow = fast.Next, slow.Next
    
17.     }
    
18.     return fast
    
19. }</font>

复制代码