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

题目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→22分步追踪移动过程3→2→0→4→2 环形链表逐轮演示第一轮移动后slow2fast0第二轮移动后slow0fast2第三轮移动后slow4fast4相遇终止判定有环Java解法1.哈希表public class Solution{ public boolean hasCycle(ListNode head){ SetListNode seen new HashSetListNode(); 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_setListNode* 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; } };