Loops in the Linked List

Description
给定链表结点类型定义，要求实现check函数返回对于给定链表是否存在环，注意链表的边界情况。

struct node{
    node *next;
    int val;
};

 

// check if there exists a loop 

bool check(node *head){

}

Hint
只需要提交check函数实现，不需要提交main函数

Problem Source: SYSU ACM/ICPC Team

zhc1:

bool check(node *head){
    node* slow = head ;
    node* fast = head?head->next:NULL; // 当head为NULL或只有1个节点时fast都为NULL
    while(  fast!=NULL && fast->next!=NULL){ 
// 有环fast就不会走到NULL，直至slow==fast；没环就会走到NULL，跳出循环
        if(slow == fast ) return true ;
        slow = slow->next ;
        fast = fast->next->next ;
    }
    return false ;
}

zhc2://代码比zhc1行数多1行，但比较次数少个1，2次，[doge]

bool check(node *head){
    if(head==NULL || head->next==NULL) return false ;
    node* slow = head ;
    node* fast = head->next;
    while(fast!=NULL && fast->next!=NULL){
        if(slow == fast ) return true ;
        slow = slow->next ;
        fast = fast->next->next ;
    }
    return false ;
}

Yizuodi的答案

bool check(node *head){
    node* slow = head;
    node* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            return true;
    }
    return false;
}