之前我的写文章《链表在STM32中的应用》
5 |& E% K) \, Q# c) W6 W
, A2 Q. J( m0 |
    不论在面试或者刷题过程中，很大概率都会遇到环形链表这种类型的题目，例如 leetcode 141. 环形链表 以及 leetcode 142. 环形链表 II 等，本文主要介绍通过快慢指针法来解决此类题型，以供大家参考。

1 u: R+ Y+ o. M" q6 a2 y* {
; B7 w" l8 a5 X环形链表
环形链表大致样子如下图所示：

7 y% y2 J) j; x* _- w* g( R3 g. l

快慢指针法
判断链表是否是环形链表，一般通过快慢指针法。
8 b8 l) [# Y7 q5 b: a9 ]3 J

5 w& F, [: }$ _! F: ~' t操作步骤
一、分别定义两个均指向头节点的指针（fast/slow）；
! B% n/ A  Z5 c! O0 b1 ]3 Z二、快指针每次走两步，慢指针每次走一步；
/ x6 y! ~8 r+ c0 N# }5 K三、如果链表存在环，则快慢指针一定会在环中相遇。

4 c# S. b6 X4 k5 a6 s
' |# F) x) F4 ]' n! B7 J9 l: F8 J. p     如下图示，快慢指针行走的轨迹如下：
( s& M4 f9 ^3 t8 Nfaster：1--->3--->5--->7
slower：1--->2--->3--->4

: U. _0 ^. N, A1 I* Ufaster：7--->5
slower：4--->5
当他们同时到达节点 5 时，完美相遇。
% n/ X4 x- q: S* r4 |9 U4 Z" s" X
% b- i' H0 [) K

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

题目

8 ?& q8 w! Y- E2 o3 a0 d+ i

Show me the Code

1. <font face="微软雅黑" size="3">//  C 语言
   
2. bool hasCycle(struct ListNode *head) {
   
3.     /* 特判 */
   9 _6 [! O/ b) q5 `! X
4.     if (head == NULL || head->next == NULL) {
   
5.         return false;
   
6.     }
   
7.     struct ListNode *slow = head, *fast = head;
   / S, }4 C  d% N7 B: ]% F
8.     /* fast指针走过链表末端，说明链表无环*/
   
9.     while((fast != NULL) && (fast->next != NULL)) {
   0 A( P- N0 W# I: r# P3 \' g8 G& c
10.         slow = slow->next;
    4 L. |7 Z. ~2 B& w/ V# w
11.         fast = fast->next->next;
    + h. r6 b  ]2 l! D! z
12.         if(slow == fast) {
    
13.             return true;
    
14.         }
    / a9 s; w- E4 T9 }; x
15.     }
    
16.     return false;
    
17. }</font>

复制代码

1. <font face="微软雅黑" size="3"># python3
   / \9 p9 ?/ ?* q  V) F* Y, {( d' G
2. class Solution:
   $ e" j8 U0 E% B$ K9 }
3.     def hasCycle(self, head: ListNode) -> bool:
   
4.         if not head or not head.next: return False     
   . n: c8 H5 ?1 N1 {9 K
5.         slow, fast = head, head
   
6.         while fast and fast.next:
   
7.             slow = slow.next
   
8.             fast = fast.next.next
   " O0 J1 @+ ^7 m$ s0 q& O
9.             if slow is fast: return True
   " ]8 Z# I0 h  n, u1 }$ Q
10.         return False  </font>

复制代码

举例2：求入环的第一个节点
% V- d, }: t* K" s

题目

/ Q6 e" e2 t2 _6 ^+ O思路
本题除了需要判断链表是否有环外，如果有环还要求入环的第一个节点，因此是上一个题目的升级版本，还是以快慢指针中举例的那个链表作为示例，下图将描述当链表有环的时候，如何求出入环的第一个节点，见下图示：
已判断链表有环
4 E" d  P7 w) r  h
求入环的第一个节点
让慢指针重新指向链表的头节点，并让快慢指针同时每次只走一步
* |4 K2 W, g4 F' `7 ?* B0 ~" T$ F7 Ifaster：5--->6--->7
slower：1--->2--->3
; x/ K' b, _9 v/ Y0 G
继续走
7 {6 }' R/ Z7 [faster：7--->4
slower：3--->4
当他们同时到达节点 4 时，再次完美相遇。
2 t+ x" X4 @/ H  [- q8 j



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


Show me the Code

1. <font face="微软雅黑" size="3">//  c 语言
   , s# i' ]. Q0 C7 H* g
2. struct ListNode *detectCycle(struct ListNode *head) {
   : ^1 s. m1 `9 s' w1 P! H, G
3.     /* 记录是否有环 */
   1 N1 W+ o9 y& T: H5 D
4.     bool flag = false;  
   
5.     struct ListNode *slow = head, *fast = head;
   3 Z7 [" V" D0 S& R! I0 W+ O
6.     while (fast != NULL && fast->next != NULL) {
   
7.         slow = slow->next;
   
8.         fast = fast->next->next;
   2 {6 X9 K6 h  d6 p( _- S. X
9.         /* 有环则更新 flag 的值，并跳出循环寻找入环第一个节点 */
   ' h" v( L; R" A3 m7 z4 q! v
10.         if (slow == fast) {
    
11.             flag = true;
    $ l- w$ P0 v3 b% E: Y7 F2 z. q
12.             break;
    3 P9 ~, {$ w1 U5 ^! o3 \/ B2 V# |
13.         }
    3 i. V' U8 H- E2 q9 a. J
14.     }
    & v4 w; g2 w  p: z
15.     /* 无环则直接返回空 */
    + {1 Y; F$ z' i. @" E
16.     if (flag == false) {
    
17.         return NULL;
    
18.     }
    / O& U3 {" d. m' k2 U) }% t  N7 ]
19.     /* 慢指针重新指向链表头节点，快指针仍指向相遇节点 */
    
20.     slow = head;
    $ s  j: R) \/ C; D
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 语言
   8 i; Z7 J( M; e! J# ^7 E5 a+ P# r
2. 
   
3. func detectCycle(head *ListNode) *ListNode {
   ( [, l3 l6 ?$ b! A# C9 e9 r2 R" z1 v8 l
4.     slow, fast := head, head
   0 \. N8 E$ `" S; B" O+ \& @/ Z
5.     for fast != nil && fast.Next != nil {
   , ]* p0 y, s3 ?1 P: w$ h  K4 E  r; h  x
6.         fast, slow = fast.Next.Next, slow.Next
   
7.         if fast == slow {
   1 B7 n3 ^2 K# c" u0 A  @- Y' k
8.             break
   
9.         }
   
10.     }
    
11.     if fast == nil || fast.Next == nil {
    
12.         return nil
    
13.     }
    
14.     slow = head
    8 s" }( o$ }& z3 n( \
15.     for fast != slow {
    
16.         fast, slow = fast.Next, slow.Next
    
17.     }
    4 O# z! v% L; H! J# ?
18.     return fast
    5 X5 H  o8 n' s% [7 u# W
19. }</font>

复制代码

/ u$ p2 s3 _; Q7 n