信阳网站开发建设公司,网站建设电话销售话术技巧,六安市裕安区建设局网站,xrea wordpress环形链表
问题#xff1a; 给你一个链表的头节点 head #xff0c;判断链表中是否有环。 如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环#xff0c;评测系统内部使用整数 pos 来表示链表尾连接…环形链表
问题 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。 来源力扣LeetCode环形链表 思路一暴力解法 我们从头遍历链表每遍历一个节点就再从头检查该节点是否已经出现过如果直到遍历完也没出现则为false反之为true。这是我们首先可以想到的暴力解法时间复杂度O(N^2)空间复杂度O(1)。
思路二快慢指针 我们创建两个指针slow与fast,让他们同时指向头节点slow每次走一步fast每次走两步。如果循环最后的结果是 slowfast 那么链表是环如果 fastnullptr 那么链表不是环。 道理跟两个人一起跑步是一样的跑道是环状的且一直跑那么快的那个人一定会在同一起跑线开始跑后再一次追上慢的人。 代码
class Solution {
public:bool hasCycle(ListNode *head) {ListNode* slowhead;ListNode* fasthead;while(slow fast fast-next){slowslow-next;fastfast-next-next;if(slowfast){return true;}}return false;}
};易错点
链表中环的入口节点
问题 给定一个链表返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环则返回 null。 为了表示给定链表中的环我们使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。 如果 pos 是 -1则在该链表中没有环。注意pos 仅仅是用于标识环的情况并不会作为参数传递到函数中。 说明不允许修改给定的链表。 来源力扣LeetCode链表中环的入口节点 思路 先证明链表有环然后再找入口节点。假如有环那么我们一定是slow走的距离是fast走的距离的二分之一且看下图分析 代码
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* slowhead;ListNode* fasthead;while(slow fast fast-next){slowslow-next;fastfast-next-next;if(slowfast){break;}}if(fastnullptr || fast-nextnullptr){return nullptr;}slowhead;while(slow!fast){slowslow-next;fastfast-next;}return fast;}
};
