[数据结构与算法]LeetCode 142. 环形链表(快慢指针)

142. 环形链表

哈希表

思路

这种解法通过哈希表，当成环时（即再次访问到之前访问过的元素时），可以判断是环，反之则不是。

代码实现

class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        unordered_set<ListNode *> visited;
        while (head)
        {
            if (visited.count(head))
            {
                return head;
            }
            visited.insert(head);
            head = head->next;
        }
        return NULL;
    }
};

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$?? 为链表中节点的数目。我们恰好需要访问链表中的每一个节点

• 空间复杂度：$O(N)$，其中 $N$?? 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中

快慢指针

思路

通过两个指针，分别叫 $slow$ 和 $fast$，起始位置均在链表首部，$fast$ 前进 $2$ 步，$slow$ 前进 $1$ 步。如果存在环路，两者必然会相遇。一次相遇后，由下图可知 $x=z$，即从相遇点到入环点的距离，恰好等于从链表头部到入环点的距离。所以将 $fast$ 指针移到链表头部，改为每次前进一步，下一次相遇一定在环首

借用网上的图 来源：LeetCode

代码

class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        ListNode *fast = head, *slow = head;
        do
        {
            if (!fast || !fast->next)
            {
                return NULL;
            }
            fast = fast->next->next;
            slow = slow->next;
        } while (fast != slow);
        fast = head;
        while (fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

复杂度分析

• 时间复杂度：$O(N)$，其中 NN 为链表中节点的数目。在最初判断快慢指针是否相遇时，$slow$?? 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。因此，总的执行时间为 $O(N)+O(N)=O(N)$?

• 空间复杂度：$O(1)$?