題目描述
一個鏈表中包含環，請找出該鏈表的環的入口結點。
算法描述： 受之前的面試題的啟發，如果我們在一個有環的鏈表中設置兩個鏈表指針，一個快，一個慢，那么兩個鏈表指針相遇的時候，必然是位于鏈表中的某個結點，利用這個結點，當我們從這個結點開始繼續遍歷，當再一次回到這個結點的時候，我們可以統計出環中的結點數，這個時候將兩個指針重置到鏈表頭，讓其中一個結點先走夠環的結點數，然后兩個指針同時走，當兩個結點相遇的時候，這個結點就是入口結點。
代碼如下：
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; }新聞熱點
疑難解答
