南京做网站南京乐识权威,wordpress playlm版权,专业网站建设品牌策,北京网络销售公司1. 题目
给定一个有环链表#xff0c;实现一个算法返回环路的开头节点。 有环链表的定义#xff1a;在链表中某个节点的next元素指向在它前面出现过的节点#xff0c;则表明该链表存在环路。
示例 1#xff1a;
输入#xff1a;head [3,2,0,-4], pos 1
输出#xff1…1. 题目
给定一个有环链表实现一个算法返回环路的开头节点。 有环链表的定义在链表中某个节点的next元素指向在它前面出现过的节点则表明该链表存在环路。
示例 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
解释链表中没有环。进阶
你是否可以不用额外空间解决此题来源力扣LeetCode 链接https://leetcode-cn.com/problems/linked-list-cycle-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
快慢指针快的走两步慢的走一步若fastslow则存在环然后慢指针回到原点快慢都一次只走一步再次相遇的点就是环的入口具体推导过程见链表中环的检测
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *fast head, *slow head;while(fast fast-next){fast fast-next-next;slow slow-next;if(fast slow)break;}if(!fast || !fast-next)return NULL;slow head;while(fast ! slow){fast fast-next;slow slow-next;}return fast;}
};
