009、环形链表
0、题目描述
环形链表
1、法1
1、 首先判断链表有没有环,方法是快慢指针,如果有环,快指针会追上慢指针,两指针相等。
——————————————————————————————————————————————
2、我们需要证明一个数学问题,在起始点开始走和在相遇点开始走,再次相遇的地方一定是入环点。
3、于是在第一段代码的基础上,有环就加一个循环找进环点,没有环就返回空。
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode* fast = head;
struct ListNode* slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow) // 说明有环
{ //找入环点的代码
struct ListNode* curr = head;
while (curr != slow)
{
curr = curr->next;
slow = slow->next;
}
return curr;
}
}
return NULL;
}