CycleList Trap

7月 19 2014

之前总结了这种带环链表检测，包括两个链表相交，对于快慢指针如何确保找到环头还进行了proof，但是写代码的时候，还是犯了一个错误：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==NULL) return NULL;
        ListNode* slow=head, *fast=head->next;
        while(slow!=NULL && fast !=NULL)
        {
            if(slow==fast) break;
            slow=slow->next;
            if(fast->next==NULL) return NULL;
            fast=fast->next->next;
        }

        if(slow==NULL || fast ==NULL) return NULL;
        ListNode* p=head;
        while(p!=slow)
        {
            p=p->next;
            slow=slow->next;
        }
        return p;
    }

};

我把slow 和fast的起始就错开了一个结点，主要是怕后面while
会一开始误判相等而推出循环，但是这样证明fast从起点开始走2k+1， slow走k，因此结果是错的，所以必须fast slow同一起跑线，这样才公平嘛，人生也是如此。因此后面的break语句放到后面，或者while改成我很少写的
至少执行一遍的do while loop。
于是改写后的代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==NULL) return NULL;
        ListNode* slow=head, *fast=head;
        do
        {
            slow=slow->next;
            if(fast->next==NULL) return NULL;
            fast=fast->next->next;
            if(slow==fast) break;
        }while(slow!=NULL && fast !=NULL);

        if(slow==NULL || fast ==NULL) return NULL;
        ListNode* p=head;
        while(p!=slow)
        {
            p=p->next;
            slow=slow->next;
        }
        return p;
    }

};

我当时还在想如果整个就是一个循环链表，该返回什么？这个代码又会返回什么？以为测试样例不会出现，实际还真出现了，模拟一下，就是返回链表头结点作为环头，实际也是对的，链表从结点开始，第一个进入环的
就是头结点嘛~

Posted by richard爱闹 - 7月 19 2014
如需转载，请注明：本文来自 Richard

留言