)
题目LeetCode142
给定一个链表的头节点head，返回链表开始入环的第一个节点。如果链表无环，则返回null。
如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
Python解法
1.哈希表
class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: visited = [] while head: if head in visited: return head else: visited.append(head) head = head.next return None逐个遍历，重复直接为所求
2.快慢指针
class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head: return None slow = head fast = head while fast: slow = slow.next if fast.next: fast = fast.next.next else: return None if slow == fast: ptr = head while ptr != slow: ptr = ptr.next slow = slow.next return ptr return None解法二的关键在于
if slow == fast: ptr = head while ptr != slow: ptr = ptr.next slow = slow.next return ptrJava解法
1.哈希表
public class Solution{ public ListNode detectCycle(ListNode head){ ListNode pos = head; Set<ListNode> visited = new HashSet<ListNode>(); while(pos != null){ if(visited.contains(pos)){ return pos; }else{ visited.add(pos); } pos = pos.next; } return null; } }2.快慢指针
public class Solution { public ListNode detectCycle(ListNode head) { if(head == null){ return null; } ListNode slow = head; ListNode fast = head; while(fast != null){ slow = slow.next; if(fast.next != null){ fast = fast.next.next; }else{ return null; } if(slow == fast){ ListNode ptr = head; while(slow != ptr){ slow = slow.next; ptr = ptr.next; } return ptr; } } return null; } }C++解法
1.哈希表
class Solution{ public: ListNode *detectCycle(ListNode *head){ ListNode *pos = head; unordered_set<ListNode *> visited; while(pos != nullptr){ if(visited.count(pos)){ return pos; }else{ visited.insert(pos); } pos = pos->next; } return nullptr; } };2.快慢指针
class Solution{ public: ListNode *detectCycle(ListNode *head){ if(head == nullptr){ return nullptr; } ListNode *slow = head; ListNode *fast = head; while(fast != nullptr){ slow = slow->next; if(fast->next != nullptr){ fast = fast->next->next; }else{ return nullptr; } if(slow == fast){ ListNode *ptr = head; while(slow != ptr){ slow = slow->next; ptr = ptr->next; } return ptr; } } return nullptr; } };
