题解 | #判断链表中是否有环#
秒懂【环形链表判断】！超清晰图解一步步拆解。
1.思路
如下图所示，链表1不存在环（最后一个节点指向Null），而链表2存在环（最后一个节点的指针域指向了第二个节点）。
判断链表是否存在环有个小技巧：快慢指针法。定义2个指针变量（即快慢指针），初始化时快慢指针都指向头节点，每次快指针每次移动 2 个节点，慢指针每次移动 1 个节点。如果 快指针指向的节点为null或者快指针指向节点的下一个节点为空，则链表没有环；如果快慢指针相遇则有环。
假如存在以下环链表，如下图所示：
判断链表是否有环步骤如下：
第一步：定义快慢指针。
第二步：移动快慢指针。
快指针fast移动2个节点，指向0节点；慢指针slow移动1个节点，指向2节点。
快指针fast再移动两个节点，这时会指向节点2；慢指针slow移动1个节点，指向0节点。
快指针fast再移动两个节点，这时会指向节点-4；慢指针slow移动1个节点，也指向-4节点。此时快慢指向都指向-4节点，则链表存在环。
如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构
2.代码
2.1 Pthon代码
class Solution:
def hasCycle(self, head: ListNode) -> bool:
# write code here
if head is None:
return False
# 1. 定义快慢指针
fast = head
slow = head
# 2.移动快慢指针
while fast is not None and fast.next is not None:
fast = fast.next.next # 快指针每次移动2个节点（快指针每次走2步）
slow = slow.next # 慢指针每次移动1个节点（慢指针每次走一步）
if fast == slow:
return True # 快慢指针相遇，有环
# 快指针对应的节点为null 或者 快指针对应节点的下一个节点为null，则没有环
return False
2.2 Java代码
public static class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param head ListNode类
* @return boolean
*/
public boolean hasCycle(ListNode head) {
// write code here
if (head == null) {
return false;
}
// 1. 定义快慢指针
ListNode fast = head;
ListNode slow = head;
// 2. 移动快慢指针
while (fast != null && fast.next != null) {
fast = fast.next.next; //快指针每次移动2个节点（快指针每次走2步）
slow = slow.next; //慢指针每次移动1个节点（慢指针每次走一步）
if (slow == fast) {
return true;
}
}
//快指针对应的节点为null 或者 快指针对应节点的下一个节点为null，则没有环
return false;
}
}
2.3 Go代码
func hasCycle(head *ListNode) bool {
// write code here
if head == nil {
return false
}
// 1. 定义快慢指针
slow := head
fast := head
// 2. 移动快慢指针
for fast != nil && fast.Next != nil {
fast = fast.Next.Next //快指针每次移动2个节点（快指针每次走2步）
slow = slow.Next //慢指针每次移动1个节点（慢指针每次走一步）
if fast == slow {
return true
}
}
//快指针对应的节点为null 或者 快指针对应节点的下一个节点为null，则没有环
return false
}
如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构
#笔试#