网站建设设计贵吗,开发商延期交房怎么办,口碑营销的重要性,苏州比较好的互联网公司来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
给你一个链表的头节点 head #xff0c;判断链表中是否有环。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环#x…来源力扣LeetCode
描述
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意 pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。
示例 1 输入head [3,2,0,-4], pos 1
输出true
解释链表中有一个环其尾部连接到第二个节点。示例 2 输入head [1,2], pos 0
输出true
解释链表中有一个环其尾部连接到第一个节点。示例 3 输入head [1], pos -1
输出false
解释链表中没有环。提示
链表中节点的数目范围是 [0, 104]-105 Node.val 105pos 为 -1 或者链表中的一个 有效索引 。
方法一哈希表
思路及算法
最容易想到的方法是遍历所有节点每次遍历到一个节点时判断该节点此前是否被访问过。
具体地我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点如果该节点已经存在于哈希表中则说明该链表是环形链表否则就将该节点加入哈希表中。重复这一过程直到我们遍历完整个链表即可。
代码
class Solution {
public:bool hasCycle(ListNode *head) {unordered_setListNode* seen;while (head ! nullptr) {if (seen.count(head)) {return true;}seen.insert(head);head head-next;}return false;}
};执行用时20 ms, 在所有 C 提交中击败了12.32%的用户 内存消耗10.3 MB, 在所有 C 提交中击败了13.19%的用户 复杂度分析 时间复杂度O(N)其中 N 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。 空间复杂度O(N)其中 N 是链表中的节点数。主要为哈希表的开销最坏情况下我们需要将每个节点插入到哈希表中一次。 方法二快慢指针
思路及算法
本方法需要读者对「Floyd 判圈算法」又称龟兔赛跑算法有所了解。
假想「乌龟」和「兔子」在链表上移动「兔子」跑得快「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时如果该链表中没有环那么「兔子」将一直处于「乌龟」的前方如果该链表中有环那么「兔子」会先于「乌龟」进入环并且一直在环内移动。等到「乌龟」进入环时由于「兔子」的速度快它一定会在某个时刻与乌龟相遇即套了「乌龟」若干圈。
我们可以根据上述思路来解决本题。具体地我们定义两个指针一快一慢。慢指针每次只移动一步而快指针每次移动两步。初始时慢指针在位置 head而快指针在位置 head.next。这样一来如果在移动的过程中快指针反过来追上慢指针就说明该链表为环形链表。否则快指针将到达链表尾部该链表不为环形链表。 细节
为什么我们要规定初始时慢指针在位置 head快指针在位置 head.next而不是两个指针都在位置 head即与「乌龟」和「兔子」中的叙述相同
观察下面的代码我们使用的是 while 循环循环条件先于循环体。由于循环条件一定是判断快慢指针是否重合如果我们将两个指针初始都置于 head那么 while 循环就不会执行。因此我们可以假想一个在 head 之前的虚拟节点慢指针从虚拟节点移动一步到达 head快指针从虚拟节点移动两步到达 head.next这样我们就可以使用 while 循环了。
当然我们也可以使用 do-while 循环。此时我们就可以把快慢指针的初始值都置为 head。
代码
class Solution {
public:bool hasCycle(ListNode* head) {if (head nullptr || head-next nullptr) {return false;}ListNode* slow head;ListNode* fast head-next;while (slow ! fast) {if (fast nullptr || fast-next nullptr) {return false;}slow slow-next;fast fast-next-next;}return true;}
};执行用时8 ms, 在所有 C 提交中击败了92.34%的用户 内存消耗8 MB, 在所有 C 提交中击败了34.69%的用户 复杂度分析 时间复杂度O(N)其中 N 是链表中的节点数。 - 当链表中不存在环时快指针将先于慢指针到达链表尾部链表中每个节点至多被访问两次。 - 当链表中存在环时每一轮移动后快慢指针的距离将减小一。而初始距离为环的长度因此至多移动 N 轮。空间复杂度O(1)。我们只使用了两个指针的额外空间。 authorLeetCode-Solution
