描述

給一個長度為n鏈表，若其中包含環(huán)，請找出該鏈表的環(huán)的入口結點，否則，返回null。

數(shù)據(jù)范圍： n≤10000，1<=結點值<=10000

要求：空間復雜度 O(1)，時間復雜度 O(n)

例如，輸入{1,2},{3,4,5}時，對應的環(huán)形鏈表如下圖所示：

鏈表示意圖.png

可以看到環(huán)的入口結點的結點值為3，所以返回結點值為3的結點。

輸入描述：

輸入分為2段，第一段是入環(huán)前的鏈表部分，第二段是鏈表環(huán)的部分，后臺會根據(jù)第二段是否為空將這兩段組裝成一個無環(huán)或者有環(huán)單鏈表

返回值描述：

返回鏈表的環(huán)的入口結點即可，我們后臺程序會打印這個結點對應的結點值；若沒有，則返回對應編程語言的空結點即可。

示例1

輸入：{1,2},{3,4,5}
返回值：3
說明：返回環(huán)形鏈表入口結點，我們后臺程序會打印該環(huán)形鏈表入口結點對應的結點值，即3

示例2

輸入：{1},{}
返回值："null"
說明：沒有環(huán)，返回對應編程語言的空結點，后臺程序會打印"null"

示例3

輸入：{},{2}
返回值：2
說明：環(huán)的部分只有一個結點，所以返回該環(huán)形鏈表入口結點，后臺程序打印該結點對應的結點值，即2

解題思路分析：

1、根據(jù)快慢指針找到相遇點；
2、如果無環(huán)，直接返回Null，
3、有環(huán)的情況下，定義一個新指針從頭開始和快指針每次各走一步，二者相等的地方便是環(huán)的入口結點；

具體代碼實現(xiàn)如下：

public ListNode EntryNodeOfLoop(ListNode pHead) {
        boolean hasCycle = false;
        ListNode fast = pHead;
        ListNode slow = pHead;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) { //先找到鏈表相遇的地方
                hasCycle = true;
                break;
            }
        }
        if (!hasCycle) {
            return null;
        }
        ListNode prev = pHead;
        while (fast !=prev) { //一個指針從頭開始走，fast指針每次走一步，兩者相遇的地方就是入口處
            fast = fast.next;
            prev = prev.next;
        }
        return prev;
    }