企业网站的制作哪家好,网站制作技术支持,站长权重,wordpress cpanel管理后台题目描述:
给你一个链表的头节点 head #xff0c;判断链表中是否有环。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环#xff0c;评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。 示例: 提示
链表中节点的数目范围在范围 [0, 104] 内-105 Node.val 105pos 的值为 -1 或者链表中的一个有效索引
解题思路: 这个题我们把它理解为一个追击问题,定义两个快慢指针: slow,fast,两个指针同时在第一个结点开始走,slow指针每次走一步,fast指针一次走两步. 如果链表有环,当fast走到入环点,slow走到了起始到入环点的一半.继续走,当slow走到如环点时,fast已经在环内的某个位置了,假设slow与fast之间的距离为N
这时每走一步,fast与slow的距离就会减小1,当N减为0时就代表fast追到了slow,两指针相遇就说明链表有环 如果链表无环,则两指针就不会遇到
我们画个图理解一下: 代码实现: bool hasCycle(struct ListNode *head) {struct ListNode *slowhead;struct ListNode *fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast)return true;}return false;
}
