力扣141----判断链表中是否有环
题目描述:给你一个链表的头节点 head ,判断链表中是否有环。
解题思路: 使用快慢指针就可以了,快的走2步,慢的走1步,距离每次减1, 如果链表带环,一定可以追上。
bool hasCycle(struct ListNode *head)
{
struct ListNode* fast=head,*slow=head;
while(fast && fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
return true;
}
return false;
}
但是这题虽然比较简单,存在一些拓展问题。 
力扣142—返回带环链表的入环节点
题目描述:给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
解题思路:  看代码
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode* fast=head,*slow=head;
while(fast && fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
{
struct ListNode* meet=fast;
while(1)
{
if(meet==head)
return head;
meet=meet->next;
head=head->next;
}
}
}
return NULL;
}
|