给定一链表头结点,如果是环形链表,返回其入口点节点。
struct ListNode
{
int val;
ListNode *next;
ListNode(int num):val(num),next(nullptr){}
};
ListNode *cycleList(ListNode *head)
{
//老规矩
if(!head || !head->next)
return head;
ListNode *slow = head;
ListNode *fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
//相等 说明有环 将slow节点回退到起始位置,
//此时 slow 距入口点的位置 和 fast 距入口点的位置长度是一样的
//各自往后移动 相遇即可
slow = head;
while(true)
{
fast = fast->next;
slow = slow->next;
if(fast == slow)
{
return fast;
}
}
}
}
return nullptr;
}