链表中环的入口结点

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解答

快慢指针法

public ListNode EntryNodeOfLoop(ListNode pHead) {
    if (pHead == null || pHead.next == null || pHead.next.next == null) {
        return null;
    }
    ListNode slow = pHead.next, fast = pHead.next.next;
    while (fast != null) {
        if (slow == fast) {
            break;
        }
        slow = slow.next;
        if (fast.next == null) {
            return null;
        } else {
            fast = fast.next.next;
        }
    }
    fast = pHead;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4?answerType=1&f=discussion
来源：牛客网

方法一：哈希法

1. 遍历单链表的每个结点

2. 如果当前结点地址没有出现在set中，则存入set中

3. 否则，出现在set中，则当前结点就是环的入口结点

4. 整个单链表遍历完，若没出现在set中，则不存在环

   代码

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        unordered_set<ListNode*> st;
        while (pHead) {
            if (st.find(pHead) == st.end()) {
                st.insert(pHead);
                pHead = pHead->next;
            }
            else {
                return pHead;
            }
        }
        return nullptr;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)，最坏情况下，单链表的所有结点都在存入set

方法二：双指针法

若不用辅助结构set，该怎么做呢？这里画了一张图

1. 初始化：快指针fast指向头结点， 慢指针slow指向头结点
2. 让fast一次走两步， slow一次走一步，第一次相遇在C处，停止
3. 然后让fast指向头结点，slow原地不动，让后fast，slow每次走一步，当再次相遇，就是入口结点。
   如上解释：
   
   如果慢指针slow第一次走到了B点处，距离C点处还有距离Y，那么fast指针应该停留在D点处，且BD距离为Y（图中所示是假设快指针走了一圈就相遇，为了便于分析），
   也就是DB+BC=2Y，（因为fast一次走2步，慢指针一次走1步，并且相遇在C处）
   在C点处，此时慢指针slow走的点为ABC，距离为X+Y，而快指针fast走的点为ABCDBC，距离为2X+2Y，
   又因为：AB=X，BC=Y，快指针走了2次BC，所以CDB距离为X，而AB距离也为X。

代码

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode *fast = pHead;
        ListNode *slow = pHead;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }
        if (!fast || !fast->next) return nullptr;
        fast = pHead;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)