题目

142. 环形链表 II【中等】

题解

快慢指针

• 判断有环？
  快指针每次走两步，慢指针每次走一步，能相遇就有环。
• 入环点在哪？
  找到相遇位置后，固定 fast 指针，slow 指针从头结点开始，两个人一步一步走，相遇点即入环点。（可以证明）

public class Solution {public ListNode detectCycle(ListNode head) {if(head==null)return null;ListNode fast=head,slow=head;while(fast!=null&&fast.next!=null){//判断是否有环fast=fast.next.next;slow=slow.next;//找入环点if(fast==slow){slow=head;while(slow!=fast){slow=slow.next;fast=fast.next;}return slow;}}return null;}
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$

哈希表

记录每一个结点，找到第一个已经存在于哈希表中的结点，即为入环点。

public class Solution {public ListNode detectCycle(ListNode head) {if(head==null)return null;ListNode p=head;Set<ListNode>hashset=new HashSet<>();while(p!=null){if(hashset.contains(p))return p;hashset.add(p);p=p.next;}return null;}
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$

相似题目

环形链表