【LeetCode】141.环形链表、142. 环形链表 II（算法 + 图解）

Hi~！这里是奋斗的明志，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~
🌱🌱个人主页：奋斗的明志
🌱🌱所属专栏：数据结构

在这里插入图片描述

📚本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。

在这里插入图片描述

链表面试题

一、环形链表
- 1. 题目
- 2. 解析
- 3. 完整代码
二、环形链表 II
- 1. 题目
- 2. 解析
- 3. 完整代码
三、总结

一、环形链表

141.环形链表

1. 题目

在这里插入图片描述

2. 解析

【思路】

快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。

【扩展问题】

为什么快指针每次走两步，慢指针走一步可以？

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

快指针一次走3步，走4步， …n步行吗？

在这里插入图片描述

快慢指针初始化：

ListNode fast = head;：快指针从链表头部开始。
ListNode slow = head;：慢指针也从链表头部开始。

遍历过程：

while (fast != null && fast.next != null)：使用快指针和慢指针遍历链表，条件是快指针不为 null 且快指针的下一个节点也不为 null。
fast = fast.next.next;：快指针每次向前移动两步。
slow = slow.next;：慢指针每次向前移动一步。

检测环：

if (fast == slow)：在每次迭代中，检查快慢指针是否相遇。如果相遇，说明链表中存在环，返回 true。

结束条件：

如果遍历完链表（即 fast 或者 fast.next 为 null ），仍未找到相遇点，则链表中不存在环，返回 false。

总结：

该算法利用快慢指针的技巧来判断单链表中是否存在环，时间复杂度为 O(n)，空间复杂度为 O(1)，非常高效。

3. 完整代码

/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {// 定义两个指针ListNode fast = head;ListNode slow = head;// 使用快慢指针进行遍历while (fast != null && fast.next != null) {fast = fast.next.next; // 快指针每次走两步slow = slow.next; // 慢指针每次走一步if (fast == slow) { // 如果快慢指针相遇，说明有环return true;}}return false; // 遍历结束，没有环}
}

二、环形链表 II

142. 环形链表 II

1. 题目

在这里插入图片描述

2. 解析

重画链表如下所示，线上有若干个节点。记蓝色慢指针为 slow，红色快指针为 fast。初始时 slow 和 fast 均在头节点处。
在这里插入图片描述
使 slow 和 fast 同时前进，fast 的速度是 slow 的两倍。当 slow 抵达环的入口处时，fast 一定在环上，如下所示。

其中：

head 和 A 的距离为 z
弧 AB (沿箭头方向) 的长度为 x
同理，弧 BA 的长度为 y

可得：

slow 走过的步数为 z
设 fast 已经走过了 k 个环，k≥0，对应的步数为 z+k(x+y)+x
以上两个步数中，后者为前者的两倍，即 2z=z+k(x+y)+x 化简可得 z=x+k(x+y)，替换如下所示。
在这里插入图片描述
此时因为 fast 比 slow 快 1 个单位的速度，且y 为整数，所以再经过 y 个单位的时间即可追上 slow。

即 slow 再走 y 步，fast 再走 2y 步。设相遇在 C 点，位置如下所示，可得弧 AC 长度为 y。

在这里插入图片描述

因为此前x+y 为环长，所以弧 CA 的长度为 x。此时我们另用一橙色指针 ptr (pointer) 指向 head，如下所示。并使 ptr 和 slow 保持 1 个单位的速度前进，在经过 z=x+k(x+y) 步后，可在 A 处相遇。
在这里插入图片描述
再考虑链表无环的情况，fast 在追到 slow 之前就会指向空节点，退出循环即可。

在这里插入图片描述

由上一题可以求出相遇点，这里的相遇点是假设的
在这里插入图片描述

在这里插入图片描述

走不确定圈数的时候：

在这里插入图片描述

初始化指针：

ListNode fast = head;：快指针从链表头部开始。
ListNode slow = head;：慢指针也从链表头部开始。

检测环：

使用两个指针 fast 和 slow 同时遍历链表，其中 fast 每次移动两步，而 slow 每次移动一步``。
如果链表中存在环，快指针 fast 最终会追上慢指针 slow。

找出环的起始点：

一旦快慢指针相遇，就说明链表中有环。
将 slow 指针重新指向链表头部。
接着，快指针 fast 和慢指针 slow 同时每次移动一步，直到它们再次相遇。这次相遇点即为环的起始点。

返回结果：

如果找到了环的起始点，就返回这个节点；否则返回 null，表示链表中无环。

3. 完整代码

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){slow = head;while(fast != slow){fast = fast.next;slow = slow.next;}return fast;}}return null;}
}

三、总结

链表（Linked List）是最简单的线性的、动态数据结构。理解它是理解树结构、图结构的基础。
区别于数组，链表中的元素不是存储在内存中连续的一片区域，链表中的数据存储在每一个称之为「结点」复合区域里，在每一个结点除了存储数据以外，还保存了到下一个节点的指针（Pointer）。

在这里插入图片描述

由于不必按顺序存储，链表在插入数据的时候可以达到O(1)的复杂度，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（links）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。
链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。
链表通常可以衍生出循环链表，静态链表，双链表等。对于链表使用，灵活使用虚拟头结点可以简化问题。