题目
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
解题
方法一：哈希表
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def detectCycle(self, head: ListNode) -> ListNode: hush = {} cur = head while cur: if cur in hush: return cur hush[cur]=1 cur = cur.next return None
方法二：双指针(进阶：空间复杂度O(1))
首先是环内相遇
后续可以推导出z=x,让一个指针从头节点开始，另一个指针一个从第一次环内相遇开始，它们接下来第一次相遇就是环形入口节点。（具体推导见详细链接）
class Solution(object): def detectCycle(self, head): fast, slow = head, head while True: if not (fast and fast.next): return fast, slow = fast.next.next, slow.next if fast == slow: break # 这行在后面，不然开始就head==head,直接break了 fast = head while fast != slow: fast, slow = fast.next, slow.next return fast
由于开始都是head,后面的循环的写法要稍微变化一下（与环形链表1有所区别）
这种写法,只能开始都是head，这样才能保证两倍关系，由于fast一开始和slow相同,所以就不能使用while fast!=slow的写法了.
如果非要类似于环形链表 1的这种写法,slow=head,fast=head.next
那么slow走的步长的2倍还要+1
也就是说当n=1（fast绕了1圈）,此时x=z+1
下面就需要p1=fast.next
python解法
class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def detectCycle(self, head: ListNode) -> ListNode: if not head: return slow = head fast = head.next p1=None while fast and fast.next: if slow==fast: p1 = fast.next #这一步是关键 break else: slow = slow.next fast = fast.next.next if not p1: return p2 = head while p1!=p2: p1=p1.next p2=p2.next return p1
c++解法
class Solution { public: ListNode *detectCycle(ListNode *head) { if(!head){ return nullptr; } ListNode* slow=head; ListNode* fast=head; while(true){ if(!(fast->next&&fast->next->next)){ return nullptr; } slow = slow->next; fast = fast->next->next; if(slow==fast){ break; } } fast=head; while(slow!=fast){ slow=slow->next; fast=fast->next; } return slow; } };
java解法
public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow=head,fast=head; while(true){ if(fast==null||fast.next==null) return null; slow=slow.next; fast=fast.next.next; if(slow==fast) break; } fast=head; while(slow!=fast){ slow=slow.next; fast=fast.next; } return slow; } }
