分类标签：链表
难易度：中等
题目描述：
给定一个有环链表，实现一个算法返回环路的开头节点。
有环链表的定义：在链表中某个节点的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
解释：链表中没有环。
思路：快慢指针
1.利用快慢指针分别遍历链表，检测链表是否为环形链表，如果不是返回NULL值；
2.如果是环形链表，则将fast返回到头指针head的位置，fast指针和slow指针每一次移动一个位置，则第一次重叠处就是环路的交点
代码：
struct ListNode *detectCycle(struct ListNode *head) {
if(head==NULL||head->next==NULL)
return NULL;
struct ListNode *fast=head,*slow=head;
//检测是否有环路
while(fast!=NULL||fast->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
break;
if (fast == NULL || fast->next == NULL)
return NULL;
}
fast=head;
//检测环路中相交的交点
while(fast!=NULL)
{
if(fast!=slow)
{
slow=slow->next;
fast=fast->next;
}
else
return slow;
}
return 0;
}
运行结果：
运行结果
占用的时间和空间
网友评论