题目描述
一个链表中包含环，请找出该链表的环的入口结点。
算法描述： 受之前的面试题的启发，如果我们在一个有环的链表中设置两个链表指针，一个快，一个慢，那么两个链表指针相遇的时候，必然是位于链表中的某个结点，利用这个结点，当我们从这个结点开始继续遍历，当再一次回到这个结点的时候，我们可以统计出环中的结点数，这个时候将两个指针重置到链表头，让其中一个结点先走够环的结点数，然后两个指针同时走，当两个结点相遇的时候，这个结点就是入口结点。
代码如下：
public ListNode meetingNode(ListNode pHead){ if (pHead == null){ return null; } ListNode slow = pHead.next; if (slow == null){ return null; } ListNode fast = slow.next; while (slow != null && fast != null){ if (slow == fast){ return slow; } slow = slow.next; fast = fast.next; if (fast != null){ fast = fast.next; } } return null; } public ListNode EntryNodeOfLoop(ListNode pHead) { ListNode meetingNode = meetingNode(pHead); if (meetingNode == null){ return null; } int countInLoop = 1; ListNode pNode = meetingNode; while (pNode.next != meetingNode){ pNode = pNode.next; ++ countInLoop; } pNode = pHead; for (int i = 0; i < countInLoop; i++) { pNode = pNode.next; } ListNode PResult = pHead; while (pResult != pNode){ pNode = pNode.next; pResult = pResult.next; } return pResult; }新闻热点
疑难解答
