给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
方法一:双指针
分析:首先用双指针就能探测出链表是否有换,如果有环,两个指针肯定会相遇 的。
a是头结点到入口结点的距离,b是入口节点Y到相遇处Z的距离,c是环的长度减去b。
相遇时有:
S_{fast} = 2S_{slow}
假设相遇时pFast在环内转了k圈,则
a + k(b+c) + b = 2(a + b)
移项得:
a = (k-1)(b+c) + c
说明头结点X到入口结点Y的距离等于从相遇处Z开始在环内转悠k-1圈(k >= 1)后,最后从Z到Y的距离。当k =1时候,a = c,此时pFast比pSlow多走一圈
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
if(pHead==null||pHead.next==null) return null;
ListNode slow=pHead;
ListNode fast=pHead;
while (fast!=null||fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if(slow==fast){
fast=pHead;
while (slow!=fast){
fast=fast.next;
slow=slow.next;
}
}
if(slow==fast)
return fast;
}
return null;
}
}
转载于:https://www.cnblogs.com/shaer/p/10718036.html