89点班组建设网站,宁波网站建设zj95,智慧团建网页版官网,商丘软件开发题目描述 给定一个链表#xff0c;如果它是有环链表#xff0c;实现一个算法返回环路的开头节点。若环不存在#xff0c;请返回 null。 题目传送门#xff1a;面试题 02.08. 环路检测 如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链…题目描述 给定一个链表如果它是有环链表实现一个算法返回环路的开头节点。若环不存在请返回 null。 题目传送门面试题 02.08. 环路检测 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环我们使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。 如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
示例 1 输入head [3,2,0,-4], pos 1输出tail connects to node index 1解释链表中有一个环其尾部连接到第二个节点。示例 2 输入head [1,2], pos 0
输出tail connects to node index 0
解释链表中有一个环其尾部连接到第一个节点。示例 3 输入head [1], pos -1
输出no cycle
解释链表中没有环。进阶
你是否可以不用额外空间解决此题
解题思路与代码 这道题算是比较简单的一道题。检测链表是否存在环的最简单的一种方法是哈希法其次就是快慢指针法。那么前者的空间复杂度可能会高些但是代码结构简单易懂。 后者虽然说比前者稍微难点但也没有难太多多了一点点的思考量而已。
总的来说这道题是一道好题考验了你一点点的数学思维与链表的实际操作
方案一哈希法
这道题如果是单单的判断链表是否成环那这道题就是一道简单题如果还要让你去返回成环的开头节点那这道题的难度就要上升了。
对于这道题如果我们用了哈希法那就是降维打击因为我们利用unordered_set就可以直接帮你返回相同节点。 具体的代码如下
class Solution {
public:ListNode *detectCycle(ListNode *head) {unordered_setListNode* set;while(head){if(set.count(head)) return head;set.insert(head);head head-next;}return nullptr;}
};复杂度分析
时间复杂度O(n),其中n是链表节点的个数空间复杂度O(n),我们需要将链表的每一个节点放入集合中所以是O(n)
方案二 快慢指针法
先解释一下这里的快慢指针法是什么意思。在这里我们先设置两个指针p1p2。 p1一次走一格p2一次走两个。因为他们走的步数不一样所以如果链表中有环存在了话那么p1p2一定不会相等。反之如果有环那p1p2一定会相等。
那这道题的难点在成环节点在距离头节点多少位置呢首先我们要画图分析。 我们设从头节点到成环节点的距离为a成环节点到p2追到p1的距离为b被追到的p1节点距离再次回到成环节点的距离为c。 p2指针一次走两格p1指针一次走一格p2追上p1的时候p2走过的距离是p1的两倍。 p1被追到时p2走了a n(b c) bp1走了a b所以不难得出这个等式a n(b c) b 2(a b) 将这个等式变化一下便是 **a c (n-1)(bc)**么。
看着这个图我们来翻译一个这个数学等式的意思。
假设从头节点走了a步到达了成环节点。便等于我在相遇节点走了 c 步 n圈。我们在p1节点与p2节点相遇的时候再去设置一个p3节点让它等于头节点。这个时候p3也一次走一步。你看图当p3在头节点走了a步的时候是不是正好与p1在b的时候走了c步 n圈呢
具体代码如下
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* p1 head;ListNode* p2 head;while(p2){p1 p1-next;if(p2-next)p2 p2-next-next;else return nullptr;if(p1 p2) {ListNode* p3 head;while(p3!p1){p1 p1-next;p3 p3-next;}return p3;}}return nullptr;}
};复杂度分析
时间复杂度O(N),N为节点的长度。因为你在实际推演的过程中会发现p1指针走过的最长的路程也不会超过链表中节点的个数而是等于节点的个数所以时间复杂度是O(N)空间复杂度O(1),我们设置了几个变量而已没有使用额外的数据结构所以是O(1)。
总结 这道题目是一个经典的链表问题经常出现在计算机科学和软件工程的面试和教程中。 这道题目的主要意义和重要性可以从以下几个方面来看 数据结构理解与应用这道题目需要你理解和操作链表这种基础数据结构。理解数据结构的特性和操作方法是编程和算法学习的基础。 双指针技巧这道题目需要使用到双指针快慢指针的技巧。这是一个常用的算法设计策略可以帮助解决一些看似复杂的问题。 算法分析通过这道题目你需要理解和分析算法的时间复杂度和空间复杂度。这道题的解决方案有一个很好的性质它只需要常量的额外空间且时间复杂度为线性。 问题解决和调试能力这道题目也可以帮助你提升问题解决和调试的能力。理解为什么这个解决方案能够工作对于提升你的算法设计和问题解决能力是非常有帮助的。
所以这道题目的意义不仅仅是解决一个具体的问题更重要的是通过这个问题来学习和提升你的数据结构知识算法设计和问题解决能力。
最后的最后如果你觉得我的这篇文章写的不错的话请给我一个赞与收藏关注我我会继续给大家带来更多更优质的干货内容。
