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

! E/ b8 L& a' x& ~. ?( c
    不论在面试或者刷题过程中，很大概率都会遇到环形链表这种类型的题目，例如 leetcode 141. 环形链表 以及 leetcode 142. 环形链表 II 等，本文主要介绍通过快慢指针法来解决此类题型，以供大家参考。
9 g- P: f: A. I# o. w/ m

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


( [% [; }3 T5 \& f" F! ?
8 f3 U! g% ]1 r- k9 x2 o* `& O' A2 V快慢指针法
判断链表是否是环形链表，一般通过快慢指针法。


* A) |5 N' b: z: m$ p! U操作步骤
; `$ D8 s3 t* g& U1 `4 v一、分别定义两个均指向头节点的指针（fast/slow）；
二、快指针每次走两步，慢指针每次走一步；
. H$ }! J- |: k& }# C; e6 L三、如果链表存在环，则快慢指针一定会在环中相遇。

7 t* A. h2 s; Z) z2 H8 |+ A: t: l
     如下图示，快慢指针行走的轨迹如下：
faster：1--->3--->5--->7
slower：1--->2--->3--->4

1 b  Z2 d: `2 V& G; `faster：7--->5
slower：4--->5
& o8 V2 W7 l$ V, D当他们同时到达节点 5 时，完美相遇。

" [- F9 o0 f" c. ?
0 s. s0 W1 ?/ q" C8 v2 H9 x9 i
0 e9 \3 i( M1 L6 r! r举栗1：判断链表是否有环
1 ?. A1 W2 [4 c6 G7 f' y: i

题目

Show me the Code
6 e: M/ E4 `" [$ Z$ m' S

1. <font face="微软雅黑" size="3">//  C 语言
   " v1 Z5 |- n% S$ F; M1 R: A
2. bool hasCycle(struct ListNode *head) {
   & h6 Z' ~) g- @0 `
3.     /* 特判 */
   / z1 y0 j, Q2 a% g9 `! ]
4.     if (head == NULL || head->next == NULL) {
   ! h% W" D6 [1 c) @8 P' }
5.         return false;
   
6.     }
   ! d2 L. x9 v) I+ M9 d9 B1 Q
7.     struct ListNode *slow = head, *fast = head;
   
8.     /* fast指针走过链表末端，说明链表无环*/
   ) z/ ^+ K0 C5 Q! c" M
9.     while((fast != NULL) && (fast->next != NULL)) {
   ; `) t( |$ L0 o0 g$ U
10.         slow = slow->next;
    
11.         fast = fast->next->next;
    ) A* }& b8 |* X$ g$ `
12.         if(slow == fast) {
    
13.             return true;
    9 @0 X5 y. G/ [
14.         }
    + c- }  ]# n+ O0 Q4 e2 ?, I
15.     }
    
16.     return false;
    
17. }</font>

复制代码

1. <font face="微软雅黑" size="3"># python3
   5 K, s5 D- ?2 N0 E$ {/ [& S, r
2. class Solution:
   
3.     def hasCycle(self, head: ListNode) -> bool:
   1 f5 z2 G5 S4 D( P+ \
4.         if not head or not head.next: return False     
   
5.         slow, fast = head, head
   , L" K6 x$ L- h) l9 W8 ]0 v) F
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：求入环的第一个节点
% o2 A3 t' M; _* L4 y- D5 a; \+ \

题目

5 h' q- ]9 m: l% Z% X% z& p思路
; d/ i4 k& Y( o# B' i本题除了需要判断链表是否有环外，如果有环还要求入环的第一个节点，因此是上一个题目的升级版本，还是以快慢指针中举例的那个链表作为示例，下图将描述当链表有环的时候，如何求出入环的第一个节点，见下图示：
/ |/ M* m3 R* W$ T6 o已判断链表有环
7 M* _" r/ ?( ~! l" q4 b. E  k8 J/ j
0 N1 _9 [# j# a. Z) R求入环的第一个节点
4 q1 p/ H9 N) j3 l; e6 {' U, @让慢指针重新指向链表的头节点，并让快慢指针同时每次只走一步
& b9 d  @- a. Q$ ~; I, a& Z: Kfaster：5--->6--->7
; ~5 V! n! @( qslower：1--->2--->3
/ c6 V+ \8 _2 a5 h3 @
  \: z$ G1 t. y% O% ?3 Y  o1 b继续走
6 i5 F8 b# _( u# U# ffaster：7--->4
6 ~# C4 M3 r  g; J. [3 Y0 i% fslower：3--->4
: u8 e$ l- u/ O当他们同时到达节点 4 时，再次完美相遇。
; Y0 e# C, `0 u$ a
- o6 V$ c1 T8 m! N' D' a. h4 a
* X: n( F+ z, w! f


0 H  d0 t" ~! ^7 o& M因此，由上面的图可知，当判断链表有环（快慢指针相遇）之后，再让快（或者慢）指针重新指向链表头节点，另外一个指针仍保持指向不变，然后让快/慢指针同时走，且每次只走一步，当他们再次相遇时，此时相遇的节点就是入环的第一个节点。
7 E! {0 Q+ {, X! u

1 }. q7 G, R0 s8 t+ G2 g" U7 N2 UShow me the Code
1 T! M. ~8 F1 U" r9 l  U' D1 Q0 ^; i

1. <font face="微软雅黑" size="3">//  c 语言
   
2. struct ListNode *detectCycle(struct ListNode *head) {
   
3.     /* 记录是否有环 */
   3 ^2 d! h; N) |! @
4.     bool flag = false;  
   ( Q, i0 j* S& G! w) v
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 的值，并跳出循环寻找入环第一个节点 */
   / ^9 R7 j$ `1 k" q9 R
10.         if (slow == fast) {
    
11.             flag = true;
      X# ?1 h, K: U1 ~/ |: ^9 d
12.             break;
    3 B3 P1 l0 W! _# n( }) F3 V* F
13.         }
    6 o9 g) g) I4 L& `  o9 I
14.     }
    
15.     /* 无环则直接返回空 */
    ' ]5 |; A. g# z. N% p+ ~2 e
16.     if (flag == false) {
    
17.         return NULL;
    4 f- h; f; R" s" K
18.     }
    # j7 a# a* ?1 k0 M
19.     /* 慢指针重新指向链表头节点，快指针仍指向相遇节点 */
    
20.     slow = head;
    
21.     /* 快慢指针每次走一步，相遇节点即为入环第一个节点 */
    : y% R, W$ ]5 U: a
22.     while (fast != slow) {
    
23.         fast = fast->next;
    
24.         slow = slow->next;
    
25.     }
    , t5 p& k  w& [3 N
26.     return slow;
    
27. }</font>

复制代码

1. <font face="微软雅黑" size="3">//  go 语言
   
2. 
   
3. func detectCycle(head *ListNode) *ListNode {
   & D; O- U& r4 g( J  J( z
4.     slow, fast := head, head
   & \* O9 C( O3 [1 h/ _
5.     for fast != nil && fast.Next != nil {
   . @) v. K* J% A1 \$ s+ x! t- m
6.         fast, slow = fast.Next.Next, slow.Next
   9 i; ]% {+ ~2 L9 @* m2 v
7.         if fast == slow {
   
8.             break
   ( M' H9 i; ^8 Q2 `
9.         }
   5 D4 v6 Z: w& }. A: d
10.     }
    6 m* I+ M0 q9 S
11.     if fast == nil || fast.Next == nil {
    
12.         return nil
    3 H4 c" K; t$ F4 u- N
13.     }
    0 Q, a" c! H; x8 y- I- e7 O& F! W
14.     slow = head
    
15.     for fast != slow {
    9 w( r3 x. p. z9 D' V9 j4 [
16.         fast, slow = fast.Next, slow.Next
    0 U6 @; |, b& e2 q1 W: ~  U
17.     }
    1 ]2 ]. |$ l2 |( b
18.     return fast
    
19. }</font>

复制代码