快慢指针巧解链表环检测（多解）

题目Leetcode141

给你一个链表的头节点head，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回true。 否则，返回false。

示例一

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

Python解法

解法一：哈希表

class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: seen = set() while head: if head in seen: return True seen.add(head) head = head.next return False

每次遍历到一个节点时，判断该节点此前是否被访问过。

解法二：快慢指针

class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: if not head or not head.next: return False slow = head fast = head.next while slow != fast: if not fast or not fast.next: return False slow = slow.next fast = fast.next.next return True

方法二逻辑

以示例展示过程

1，带环链表演示示意图（示例链表：3→2→0→4→2）

2，分步追踪移动过程（3→2→0→4→2 环形链表逐轮演示）

第一轮：移动后：slow=2，fast=0

第二轮：移动后：slow=0，fast=2

第三轮：移动后：slow=4，fast=4

相遇终止（判定有环）

Java解法

1.哈希表

public class Solution{ public boolean hasCycle(ListNode head){ Set<ListNode> seen = new HashSet<ListNode>(); while(head != null){ boolean isAddSuccess = seen.add(head); // add失败，说明当前节点已经在集合中，链表有环 if(!isAddSuccess){ return true; } head = head.next; } return false; } }

2.快慢指针

public class Solution { public boolean hasCycle(ListNode head) { if(head == null || head.next == null){ return false; } ListNode slow = head; ListNode fast = head.next; while(slow != fast){ if(fast == null || fast.next == null){ return false; } slow = slow.next; fast = fast.next.next; } return true; } }

C++解法

1.哈希表

class Solution{ public: bool hasCycle(ListNode *head){ unordered_set<ListNode*> seen; while(head != nullptr){ if(seen.count(head)){ return true; } seen.insert(head); head = head->next; } return false; } };

2.快慢指针

class Solution { public: bool hasCycle(ListNode *head) { if (head == nullptr || head->next == nullptr) { return false; } ListNode* slow = head; ListNode* fast = head->next; while (slow != fast) { if (fast == nullptr || fast->next == nullptr) { return false; } slow = slow->next; fast = fast->next->next; } return true; } };