链表有环问题

问题1: 给定一个链表,判断这个链表是否有环

原理:使用快慢指针法,如果链表有环,则必定存在两个指针相等.

typedef int ElementType;
struct Node{
    ElementType data;
    struct Node* next;
};
typedef struct Node* PNode;
typedef PNode List;

/**
 * 判断一个链表是否有环
 * @param list
 * @return 0 :无, 1:有
 */
int existLoop(List list){
    if(list == NULL) return 0;
    PNode fast , slow;
    slow = fast = list;
    while (fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){
            return 1;
        }
    }
    return 0;
}

问题2: 如果链表有环,找出环的入口节点

对于有环的链表,使用快慢指针法(快指针的速度=2 倍慢指针的速度),当第一次相遇的节点一定在环上,相遇的结点到环的入口距离与链表入口点到环入口结点距离相等

PNode getEntreLoop(List list){
    if(list == NULL) return 0;
    PNode fast , slow;
    slow = fast = list;
    while (fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){
            //快慢指针第一次相遇的节点
            break;
        }
    }
    
    PNode ptr01 = slow , ptr02 = list;
    while (fast->next != NULL){
        ptr01 = ptr01->next;
        ptr02 = ptr02->next;
        if(ptr01 == ptr02){
            printf("\n找到环的入口点:%d\n",ptr02->data);
            return ptr02;
        }
    }
    return NULL;
}

问题3: 环有多长

原理:快慢指针第一遍相遇后,然后在进行第二遍循,当快慢指针再一次相遇时,记录慢指针走的步数就是,环的长度.

int getLoopLen(List list){
    if(list == NULL) return 0;
    PNode fast , slow;
    slow = fast = list;
    while (fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){
            //快慢指针第一次相遇的节点
            break;
        }
    }
 
     int len = 0;   
 
    while (fast->next != NULL){
        len++;
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){
         //快慢指针第二次相遇的节点
         return len;
        }
    }
    return 0;
}