142. Linked List Cycle II 第二种方法,第二个if

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow=head;
        ListNode *fast=head;
        ListNode *meet=NULL;
        while(fast){
            slow=slow->next;
            fast=fast->next;
            if (!fast){
                return NULL;//要么到链尾退出循环
            }
            fast=fast->next;
            if(fast==slow){//要么找到相遇点退出
                meet=fast;
                break;
            }
        }
        if (meet==NULL){//为什么这里的if判断不能省略
            return NULL;
        }
        while(meet){
            if (head==meet){
                return head;
            }
            head=head->next;
            meet=meet->next;
        }        
    }
};
采用第二种方法,为什么第二个if判断不能省略掉?当meet依然为NULL时,不就表明链表为单链表没有环。可是在上一步while(fast)循环中没有找到meet,这时候fast不就指向链表结尾,返回NULL结束了?求解释。

林沐

赞同来自: 胡浪

同学你说的对!  我的原意是当链表没有环时,跳出循环会有两种可能, 第一:从while(fast)这里跳出循环, 第二:从if (!fast){return NULL;//要么到链尾退出循环}   这两个都是因为链表没有环才跳出的循环。 那么第一种:从while(fast)这里跳出循环是因为链表无环且链表节点个数为偶数个!那么if (meet==NULL){//为什么这里的if判断不能省略 ,这里我是想直接返回了,实际上可以让它在结尾直接返回。 那么第二种:从从if (!fast){return NULL;//要么到链尾退出循环}这里跳出循环是因为链表无环且链表节点个数为奇数个!   所以结论是,我的代码那个if判断确实冗余了!赞仔细的同学。 这个问题我会在本周四的答疑课上也会讲一下。      

要回复问题请先登录注册