算法1
快慢指针
先快慢指针判断是不是有环
如果有环,两个指针指向的节点一定是在环中相遇,然后一个不动,另一个继续移动,再次相遇便可以知道,环中有几个节点了
然后一个指针指向头结点,另一个指针指向在头结点后面的环中节点数量的那个节点,两个节点傍地走,一起移动,就会在环的入口相遇了
Java 代码
class Solution {
public ListNode entryNodeOfLoop(ListNode head) {
ListNode meet = meetNodeOfLoop(head);
if(meet==null) return null;
int num = 1;
ListNode node = meet.next;
while(node!=meet){
num++;
node = node.next;
}
node = head;
for(int i = 0; i < num ; i++){
node = node.next;
}
// num=0;
ListNode node_ = head;
while(node!=node_){
node= node.next;
node_ = node_.next;
}
return node;
}
public ListNode meetNodeOfLoop(ListNode head) {
if(head == null)
return null;
ListNode slow = head;
ListNode fast = slow.next;
// System.out.println(fast.val);
while(slow!=null&&fast!=null){
if(slow == fast){
return fast;
}
slow = slow.next;
fast = fast.next;
if(fast!=null)
fast=fast.next;
}
return null;
}
}
666