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


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

+ X" _& D1 D1 Q3 j
) R1 Z# e+ K! D4 D环形链表
环形链表大致样子如下图所示：
5 ~- R  K6 ~2 ]% H* U( [9 K: b


, D4 d7 q& s1 _# b& N8 P快慢指针法
判断链表是否是环形链表，一般通过快慢指针法。


操作步骤
3 V+ T( W7 {7 `: K5 v  I: D一、分别定义两个均指向头节点的指针（fast/slow）；
二、快指针每次走两步，慢指针每次走一步；
# ?, h% N6 O7 a7 M5 a三、如果链表存在环，则快慢指针一定会在环中相遇。


     如下图示，快慢指针行走的轨迹如下：
faster：1--->3--->5--->7
3 [! F" w: E( K4 ^, l& xslower：1--->2--->3--->4

$ `* Z' K8 Y: R; `; ~faster：7--->5
! b! R) O) L7 f! Uslower：4--->5
9 p+ ~+ T) k& r' ?' q当他们同时到达节点 5 时，完美相遇。

, c! C9 D. e6 H3 F- U

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

/ g4 n" j' ~8 N

题目

9 |/ Q7 c% K3 G3 C3 k5 \

Show me the Code
, h# y2 ^7 z- {- w% F& j

1. <font face="微软雅黑" size="3">//  C 语言
   ' `/ x$ r7 q1 ~. V5 U+ u
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;
    5 ^0 E5 ]; e8 M) a
11.         fast = fast->next->next;
    0 c- S1 N% S" E! A% m  c
12.         if(slow == fast) {
    " M7 K3 `* ~) {2 X* Y1 ^
13.             return true;
    
14.         }
    6 ~- |. L" t( ?  G4 O  U) B
15.     }
    , a+ q/ X; k; P1 i' `* ~, Q
16.     return false;
      B. L3 z) e0 b; W
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     
   , ?, h9 k+ C3 W( A: h, Q+ A
5.         slow, fast = head, head
   ' w* g5 @+ N- C1 p- z
6.         while fast and fast.next:
   5 r9 x+ T. Q! d! P8 z/ [& h
7.             slow = slow.next
   
8.             fast = fast.next.next
   
9.             if slow is fast: return True
   
10.         return False  </font>

复制代码

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

题目

1 ^7 u: ?, G  A7 M, Z  E
思路
5 o" S1 {6 D" M本题除了需要判断链表是否有环外，如果有环还要求入环的第一个节点，因此是上一个题目的升级版本，还是以快慢指针中举例的那个链表作为示例，下图将描述当链表有环的时候，如何求出入环的第一个节点，见下图示：
已判断链表有环

. |" Z( y3 ~# {6 f求入环的第一个节点
8 |' u* l5 b# a" w让慢指针重新指向链表的头节点，并让快慢指针同时每次只走一步
faster：5--->6--->7
) s( ^3 n% R! g* e$ Q9 t; Y2 \slower：1--->2--->3
' n6 x' {3 |7 |9 d4 F! O3 E- B
8 d$ M. o# E- `0 X7 p继续走
  H7 X5 ]: u% F: e2 v. f7 x% R3 Wfaster：7--->4
slower：3--->4
当他们同时到达节点 4 时，再次完美相遇。

  c. i8 b- E3 D" L6 r$ v5 a% K

8 D# ]3 E. m4 {2 U, |0 P

4 u$ v( A. ?/ j6 V- A因此，由上面的图可知，当判断链表有环（快慢指针相遇）之后，再让快（或者慢）指针重新指向链表头节点，另外一个指针仍保持指向不变，然后让快/慢指针同时走，且每次只走一步，当他们再次相遇时，此时相遇的节点就是入环的第一个节点。
' {$ c6 [  z/ i9 z6 ?

% ^/ r& w" K" DShow me the Code
/ U# J  }" q0 T$ n5 K2 b0 `

1. <font face="微软雅黑" size="3">//  c 语言
     V6 y3 q8 j0 {8 A, `
2. struct ListNode *detectCycle(struct ListNode *head) {
   
3.     /* 记录是否有环 */
   
4.     bool flag = false;  
   ( J+ t7 V5 N& X+ Y
5.     struct ListNode *slow = head, *fast = head;
   : H/ B+ ^! k/ e. n8 c3 M7 v1 S
6.     while (fast != NULL && fast->next != NULL) {
   8 [" h1 \* o8 G* ~) i9 F# u" A
7.         slow = slow->next;
   ' f% h" V  e% m( O7 W
8.         fast = fast->next->next;
   ( y; `4 r. N  w
9.         /* 有环则更新 flag 的值，并跳出循环寻找入环第一个节点 */
   
10.         if (slow == fast) {
    
11.             flag = true;
    / r' }. |& Z; a7 z/ Y5 A# m0 r* {5 B
12.             break;
    
13.         }
    5 c2 w( K" J. h# ~( Q
14.     }
    
15.     /* 无环则直接返回空 */
    . \" U5 g/ r7 f! z$ ^; K
16.     if (flag == false) {
    8 ~. K+ M! L$ G' d0 k; [
17.         return NULL;
    & F( o8 D- d: Q- y
18.     }
    
19.     /* 慢指针重新指向链表头节点，快指针仍指向相遇节点 */
    : X2 ]: I+ K) b, X2 j
20.     slow = head;
    , @% O$ Z& A: h# V
21.     /* 快慢指针每次走一步，相遇节点即为入环第一个节点 */
    
22.     while (fast != slow) {
    4 j9 |- H7 n" W9 J5 |
23.         fast = fast->next;
    
24.         slow = slow->next;
    - {2 \2 N& t% n, T1 Q
25.     }
    
26.     return slow;
    
27. }</font>

复制代码

1. <font face="微软雅黑" size="3">//  go 语言
   
2. 
   # W) u9 F! p  u) X
3. func detectCycle(head *ListNode) *ListNode {
   
4.     slow, fast := head, head
   ! _" h) S) V8 {/ Y. l5 l3 l
5.     for fast != nil && fast.Next != nil {
   
6.         fast, slow = fast.Next.Next, slow.Next
   , A& C2 j. k& j! H
7.         if fast == slow {
   
8.             break
   
9.         }
   2 l2 X: }6 X+ p2 ?5 T. ~' Y
10.     }
      u6 R4 X. b2 S7 [. C1 k
11.     if fast == nil || fast.Next == nil {
    3 p! A: x2 v) P1 U: _
12.         return nil
    $ I' u/ y' o) Z7 g& E. m
13.     }
    
14.     slow = head
    6 e! M& ?4 }8 l" |$ o
15.     for fast != slow {
    
16.         fast, slow = fast.Next, slow.Next
    ) G$ j* [: _+ H) k2 K
17.     }
    % ]' W* t; N/ ~. @
18.     return fast
    ! M4 s& u' I9 D2 u
19. }</font>

复制代码

& S6 J3 e% T3 V( R/ @( z( d