Java1(快慢指针)
时间复杂度:$O(n)$
空间复杂度:$O(1)$
思路:
用两个指针$p, q$分别从起点开始走,$p$ 每次走一步,$q$ 每次走两步。
如果过程中 $q$ 走到null,则说明不存在环。否则当 $p$ 和 $q$ 相遇后,让 $p$ 返回起点,$q$ 待在原地不动,然后两个指针每次分别走一步,当相遇时,相遇点就是环的入口。
class Solution {
public ListNode entryNodeOfLoop(ListNode head) {
ListNode p = head;
ListNode q = head;
while(p != null && q != null) {
p = p.next;
q = q.next;
if(q != null) q = q.next;
else return null;
if(p == q) {
p = head;
while(p != q) {
p = p.next;
q = q.next;
}
return p;
}
}
return null;
}
}
Java2$(HashSet)$
时间复杂度:$O(n)$
空间复杂度:$O(n)$
思路:
遍历链表,如果当前节点未访问过,就加入$HashSet$。否则,当前节点访问过,就返回该节点(即环的入口结点)。
class Solution {
public ListNode entryNodeOfLoop(ListNode head) {
HashSet<ListNode> set = new HashSet<>();
while(head != null) {
if(set.contains(head)) {
return head;
}
set.add(head);
head = head.next;
}
return null;
}
}