剑指23：链表中环的入口节点

传送门

nowcoder
leetcode

题目描述

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

C++ 代码 - nowcoder

/*
    哈希表
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if (pHead == nullptr) return nullptr;

        unordered_map<ListNode*, int> map;
        ListNode* p = pHead;
        while (p != nullptr) {
            map[p] ++;
            if (map[p] == 2) return p;
            p = p->next;
        }
        return nullptr;
    }
};

/*
    快慢指针

	fast、slow 同时从一个链表的头部出发，fast 一次走 2 步，slow 一次走 1 步。
	如果该链表有环，两个指针必然在环内相遇。
	此时，把一个指针重新指向链表头部，另一个不变（还在环内）。
	两个指针一次走 1 步，相遇的地方就是入口节点。

    证明略
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if (pHead == nullptr || pHead->next == nullptr) return nullptr;

        ListNode *fast = pHead, *slow = pHead;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }

        if (fast == nullptr || fast->next == nullptr) return nullptr;
        slow = pHead; // slow 从链表头出发，fast 从相遇点出发
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

C++ 代码 - leetcode

/*
    快慢指针

	fast、slow 同时从一个链表的头部出发，fast 一次走 2 步，slow 一次走 1 步。
	此时，把一个指针重新指向链表头部，另一个不变（还在环内）。
	两个指针一次走 1 步，相遇的地方就是入口节点。
*/
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) return nullptr;

        ListNode *fast, *slow;
        fast = slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }

        if (fast == nullptr || fast->next == nullptr) return nullptr; // fast 为空指针说明没有环

        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};