环形链表

发布时间 2023-04-27 15:45:14作者: 该说不唠

题目:给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

 思路:

1、判断是否有环

定义两个指针,一快一慢,从头指针开始遍历,快指针不为空或者快指针的下一个结点不为空,则有环

2、返回环的位置

 

找到快、慢指针相遇的点,根据公式x=(n-1)(z+y)+z,n-1代表快指针转了多少圈,则x=z。

再定义两个指针,一个从头结点开始,另一个从fast指针与slow指针相遇的结点开始,两个指针相等时,为环形入口结点。

需要注意的点:

1、

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast!=NULL&&fast->next!=NULL)//如果有环则在循环内部,无环则跳出循环
        {
            fast=fast->next->next;
            slow=slow->next;

            if(fast==slow)
            {
                ListNode* index1=fast;//快慢指针均可,因为接下来要步进一个指针
                ListNode* index2=head;

                while(index1!=index2)
                {
                    index1=index1->next;
                    index2=index2->next;
                }

                return index2;
            }



        }

        return NULL;
        
    }
};