每日算法-9 环形列表

问题

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

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

示例 1:

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

《每日算法-9 环形列表》

示例 2:

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

《每日算法-9 环形列表》

示例 3:

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

《每日算法-9 环形列表》

进阶:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/linked-list-cycle

分析

首先,来摸清一下题型中所提到的环形结构

//Definition for a singly-linked list.
class ListNode { 
    public $val = 0;
    public $next = null;
    function __construct($val) {  $this->val = $val; }
}

题目中,创建了一个类,叫做ListNode,代表环形中的节点,如果想要完成题干中 示例1 的环形结构,代码应是这样子的:

$first = new ListNode(3);	//创建第一个节点$first
$second = new listNode(2);	//创建第二个节点$second
$first->next = $second;	   //建立关联:$first的下一个节点是$second

$third = new listNode(0);	//创建第三个节点$third
$second->next = $third;		//建立关联:$second的下一个节点是$third

$fourth = new listNode(-4);	 //创建第四个节点$fourth
$third->next = $fourth;		//建立关联:$third的下一个节点是$fourth

$fourth->next = $second;	//建立关联:$fourth的下一个节点是$second,形成闭环

最后,传进Solution类中hasCycle()方法的参数便是上文所述的$first

《每日算法-9 环形列表》

理解了数据的结构,接下来就来看是我们的正式答题

解法

一、哈希表

分析:

遍历所有结点时,在哈希表中存储每个结点,如果当前结点为null不存在,那么我们已经遍历完整个链表,并且该链表不是环形链表。如果当前结点已经存在于哈希表中,那么代表该链表是环形链表,返回 true。

代码如下:

class Solution { 
    /** * @param ListNode $head * @return Boolean */
    function hasCycle($head) { 
        //哈希表,记录节点的内存地址
        $nodesSeen = [];
        //第一个节点进入,肯定是存在的,$head随着遍历,会被替换成下一个节点
        while ($head != null) { 
            //如果哈希表中已经记录了这一个节点,那么代表存在了闭环
            if (in_array($head, $nodesSeen)) { 
                return true;
            } else { 
                //记录节点
                $nodesSeen[] = $head;
            }
            //替换为下一个节点
            $head = $head->next;
        }
        //如果最后一个节点为null,则会来到这里,代表不是闭环
        return false;
    }
}

提交结果:
《每日算法-9 环形列表》

复杂度分析:

该算法中,对于含有 n 个元素的链表,我们访问每个元素最多一次。添加一个结点到哈希表中只需要花费 O(1)的时间。即时间复杂度为O(n)

而使用的空间取决于添加到哈希表中的元素数目,最多可以添加 n 个元素,即空间复杂度为O(n)

二、双指针

分析:

假设有两个在环形赛道上跑步的运动员(分别称之为 跑得慢跑得快 ),跑得慢跑一步的时候,跑得快就跑了两步。这种情况下,跑得快最终一定会追上跑得慢。为什么?分析下情况:

  • 某次循环中,如果跑得快只落后跑得慢一步,在下一次迭代中,他们就会分别跑了一步或两步并且相遇。
  • 就算跑得快跑得慢在本次循环中没有相遇,但是他们的距离确实在一步步的靠近(这是环形跑道,跑得快早晚能领先跑得慢一圈后相遇)
  • 如果这不是环形跑道,那么当跑得快跑到终点时,则结束,我们可以返回false

使用这两个具有不同速度的快、慢两个指针来遍历链表,我们只需要记录 快指针 和 慢指针 两个变量,那么空间复杂度可以被降低至 O(1)。

代码如下:

class Solution
{ 
    /** * @param ListNode $head * @return Boolean */
    function hasCycle($head)
    { 
        //如果节点不存在 或 节点不存在下一个节点,那么肯定没有环形结构
        if ($head == null || $head->next == null) { 
            return false;
        }

        //设置慢指针为当前节点
        $slow = $head;
        //设置快指针为下一个节点
        $fast = $head->next;

        //如果慢指针和快指针是同一个节点,则代表属于环形结构,结束循环
        while ($slow != $fast) { 
            //如果快指针已经跑完了,没有下一个节点,那么不是环形结构
            if ($fast == null || $fast->next == null) { 
                return false;
            }
            //慢指针每次走一步,走到下一个节点
            $slow = $slow->next;
            //快指针每次走两步,走到下下一个节点
            $fast = $fast->next->next;
        }
        return true;
    }
}

提交结果:
《每日算法-9 环形列表》

附录

这里补充一下LeetCode内部对节点进行的处理方法。

输入:head = [3,2,0,-4], pos = 1,然后形成示例相关的结构

function listNodeCreation(array $head, $pos)
{ 
    //如果不存在任何节点,直接返回false
    if (empty($head)) { 
        return null;
    }

    //开始的节点
    $headNode = new ListNode(array_shift($head));
    $nextNode = &$headNode;

    //记录最终要用于循环的节点
    $circleNode = $pos === 0 ? $headNode : null;

    foreach ($head as $i => $node) { 
        $nextNode->next = new ListNode($node);
        //记录为下一个节点
        $nextNode = &$nextNode->next;

        if ($i + 1 === $pos) { 
            $circleNode = &$nextNode;
        }
    }

    //最终合并
    $nextNode->next =& $circleNode;

    return $headNode;
}


$head = listNodeCreation([3, 2, 0, -4], 1);
print_r($head->next->next->next);
    原文作者:MillionMile
    原文地址: https://blog.csdn.net/weixin_38125045/article/details/107314035
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞