剑指offer: 链表中环的入口节点
题目描述:给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
快慢指针追赶问题:
定义快慢指针 快指针每次走两步,慢指针每次走一步
fast = fast->next->next;
slow = slow->next;
这样的话,如果链表存在环,那么fast指针比slow指针先入环 ,并且slow指针没有走完环一圈之前,fast指针就可以追上slow指针,而如果fast指针或者slow指针任何一个指针的指向为空的话,说明链表中不存在环,直接返回。
此时 fast==slow , 说明环存在,此时遍历这个环,满足条件(slow != fast) 那么就找了入口节点。
struct ListNode
{
int val;
struct ListNode *next;
ListNode(int x)
:val(x), next(NULL)
{}
};
class Solution {
public:
ListNode * EntryNodeOfLoop(ListNode* pHead)
{
//快慢指针 快指针一次走两步 慢指针一次走一步
ListNode* fast = pHead;
ListNode* slow = pHead;
while (fast != nullptr&&fast->next != nullptr)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
{
break;
}
}
//如果如果找到环的话 再次遍历链表 输出慢指针即可
fast = pHead;
if (fast == nullptr || fast->next == nullptr)
return nullptr;
while (fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
};