题目:一个链表中包含环,请找出该链表的环的入口结点。
判断一个链表是否有环,可以用快慢指针来判断,开始的时候快慢指针都指向头结点,慢指针一次走一个,快指针一次走两个,当他们相遇的时候说明此链表有环,并且相遇的结点一定是在环中。可以从这个结点出发,一遍继续向前移动一边计数,当再次回到这个结点的时候,就能得到环中的结点数了。其实就像操场跑圈一样,跑得快的和跑的慢的人相遇,跑得快的要不是比慢的多跑一圈要么多跑n圈。当确定链表有环以后,可以将慢指针从头指针开始,快指针还在相遇的位置开始,快慢指针每次都向前移动一个,再次相遇的时候就是环的入口结点。
代码如下:
public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { if(pHead==null||pHead.next==null) return null; ListNode faster=pHead; ListNode slow=pHead; while(faster!=null&&faster.next!=null){ slow=slow.next; faster=faster.next.next; if(slow==faster){ slow=pHead; while(slow!=faster){ slow=slow.next; faster=faster.next; } if(slow==faster) return slow; } } return null; } }