每日一练--环形链表

力扣142

对于环形链表来说,我们可以设置两个指针,一个快指针和一个慢指针

当快指针向前移动两步的时候,慢指针使其向前移动一步,这样相当于快指针始终在以一步接近慢指针,那么快慢指针在有环的时候一定是在环中相遇的,并且环的入口就是相遇的位置继续向前与指针从头结点开始一步步向前后相遇的位置.

代码如下

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode * Fast = head;
        ListNode * Slow = head;
        while (Fast != NULL && Fast->next != NULL){
            Slow = Slow->next;
            Fast = Fast->next->next;
            if(Fast == Slow){
                ListNode * Index1 = Fast;
                ListNode * Index2 = head;
                while(Index1 != Index2){
                    Index1 = Index1->next;
                    Index2 = Index2->next;
                }
                return Index2;
            }
        }
        return NULL;
    }
};