LeetCode#141-Linked List Cycle-环形链表

一、题目

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例3:

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

进阶:你能用 O(1)(即,常量)内存解决此问题吗?

二、题解

  • 解法1:哈希表

遍历所有节点并把每个节点的引用存储到哈希表中。如果当前节点的引用已经存在于哈希表中,说明该链表是环形链表,返回 true;反之,则遍历到尾,即该节点的下一个节点为 null,该链表不是环形链表,返回 false。

时间复杂度:O(n),空间复杂度:O(n)。

function hasCycle($head) {
    $hashMap = [];
    $curr = $head;
    while ($curr != null && $curr->next != null) {
        if (in_array($curr, $hashMap)) {
            return true;
        } 
        $hashMap[] = $curr;
        $curr = $curr->next;
    } 
    return false;
}
  • 解法2:双指针——快慢指针

快指针:一次两步
慢指针:一次一步

假设一个环形赛道,两个运动员 A 和 B,A 领先 B 一步:
在一个圆里,速度快的 A 在跑了 n 圈后,一定能遇到速度慢的 B
——对应链表,就是两个指针重合

如果不是圆,速度快的 A 一定先到达终点,则说明不存在环
——对应链表,就是结尾指针指向null

时间复杂度:O(n),空间复杂度:O(1)。

function hasCycle($head) {
    if ($head == null || $head->next == null) {
        return false;
    }
    //快慢指针
    $slow = $head;
    $fast = $head->next;
    while ($slow != $fast) {
        //没有环,fast走到链表尾部,fast为空或者fast的next为空
        if ($fast == null || $fast->next == null) {
            return false;
        }
        $slow = $slow->next;
        $fast = $fast->next->next;
    }
    return true;
}

快慢指针法是看了题解后做出来的,一开始有点不明白:为什么快指针速度为 2,慢指针速度为 1?快指针速度不能为 3 甚至更大吗?

画图画了几遍,大概理解了:
fast 走 2 步,slow走 1 步,如果有环,则 fast 会碰到 slow 或者 fast 会走到 slow 的后面。

如果是 fast 走到 slow 后面,这时候两个指针每走一次它们之间的距离就会缩小 1,最后无论多远两个指针肯定会相遇。

但是如果是 fast 走 3 步,slow 走 1 步,同样是前面的情况,它们之间的距离每次缩小 2,最后 fast 又跑到 slow 前面去了,所以如果 fast 设置为 3,需要多加一个判断条件,见下面代码 while 处。

function hasCycle($head) {
    if ($head == null || $head->next == null) {
        return false;
    }
    //快慢指针
    $slow = $head;
    $fast = $head->next->next;
    while ($slow != $fast || $slow->next != $fast) {
        //没有环,fast走到链表尾部,fast为空或者fast的next为空
        if ($fast == null || $fast->next == null) {
            return false;
        }
        $slow = $slow->next;
        $fast = $fast->next->next->next;
    }
    return true;
}
原文地址:https://www.cnblogs.com/sunshineliulu/p/12688898.html