单链表之环形链表

• 2021 年 2 月 17 日
• 筆記

    不论在面试或者刷题过程中，很大概率都会遇到环形链表这种类型的题目，例如 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

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

题目

思路

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

已判断链表有环

求入环的第一个节点

让慢指针重新指向链表的头节点，并让快慢指针同时每次只走一步

faster：5—>6—>7

slower：1—>2—>3

继续走

faster：7—>4

slower：3—>4

当他们同时到达节点 4 时，再次完美相遇。

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

Show me the Code