链表中环的入口结点
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
//设置快慢指针
//快指针一次走两步,慢指针一次走一步
ListNode fastHead = pHead;
ListNode lowHead = pHead;
boolean flag=false;
while (fastHead != null && fastHead.next != null) {
lowHead=lowHead.next;
fastHead=fastHead.next.next;
if(fastHead==lowHead){
//说明有环
flag=true;
break;
}
}
//无环情况
if(!flag)
return null;
// 有环慢指针从头开始,相交点就是入口节点
lowHead=pHead;
while(fastHead!=lowHead){
fastHead=fastHead.next;
lowHead=lowHead.next;
}
return lowHead;
}
}
public ListNode EntryNodeOfLoop(ListNode pHead) {
//设置快慢指针
//快指针一次走两步,慢指针一次走一步
ListNode fastHead = pHead;
ListNode lowHead = pHead;
boolean flag=false;
while (fastHead != null && fastHead.next != null) {
lowHead=lowHead.next;
fastHead=fastHead.next.next;
if(fastHead==lowHead){
//说明有环
flag=true;
break;
}
}
//无环情况
if(!flag)
return null;
// 有环慢指针从头开始,相交点就是入口节点
lowHead=pHead;
while(fastHead!=lowHead){
fastHead=fastHead.next;
lowHead=lowHead.next;
}
return lowHead;
}
}
全部评论
相关推荐