問題1: 給定一個(gè)鏈表,判斷這個(gè)鏈表是否有環(huán)

原理:使用快慢指針法,如果鏈表有環(huán),則必定存在兩個(gè)指針相等.

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

/**
 * 判斷一個(gè)鏈表是否有環(huán)
 * @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: 如果鏈表有環(huán),找出環(huán)的入口節(jié)點(diǎn)

image.png

如上圖所示，依然使用快門指針法(快指針的速度=2 倍慢指針的速度)超凳，當(dāng)兩個(gè)指針第一次相遇時(shí)，設(shè)相遇點(diǎn)為X,
M->P：設(shè)為a, P->X：設(shè)為b，X->P設(shè)為c。

首先可以肯定的是剃诅，第一次相遇時(shí)，慢指針不可能在環(huán)里運(yùn)動(dòng)超過一圈：
證明：設(shè)慢指針到達(dá)入口p點(diǎn)時(shí)驶忌，快指針在環(huán)內(nèi)的某個(gè)位置P0矛辕，設(shè)環(huán)長(zhǎng)度為m, 則此時(shí)P0->P的距離肯定是小于m的笑跛，當(dāng)慢指針運(yùn)動(dòng)一圈時(shí)走的距離為m, 而快指針此時(shí)走了2m，就是說快指針早就追趕上了慢指針聊品。即兩者相遇時(shí)慢指針不可能運(yùn)動(dòng)超過一圈飞蹂。

有了上面的結(jié)論，我們假設(shè)當(dāng)?shù)谝淮蜗嘤鰰r(shí)翻屈，快指針已經(jīng)在環(huán)里運(yùn)行了n圈陈哑，因此其走的距離為n*(b+c) + b+a，慢指針運(yùn)動(dòng)的距離為a+b, 由于快指針的運(yùn)動(dòng)速度時(shí)慢指針的2倍伸眶，得如下等式

2*(a+b) = n*(b+c)+b +a   =>  a+b=n(b+c)   => a = (n-1)(b+c) + c

從上面的等式關(guān)系惊窖，我們可以得出以下結(jié)論：

1. 第一次相遇時(shí)，慢指針走的距離一定是環(huán)長(zhǎng)度的整數(shù)倍
2. 第一次相遇后厘贼，若有兩個(gè)速度相同的指針界酒，一個(gè)從M點(diǎn)出發(fā)，一個(gè)從X點(diǎn)出發(fā)嘴秸，繼續(xù)運(yùn)動(dòng)毁欣，則二者一定會(huì)在P點(diǎn)發(fā)生相遇。

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){
            //快慢指針第一次相遇的節(jié)點(diǎn)
            break;
        }
    }
    
    PNode ptr01 = slow , ptr02 = list;
    while (fast->next != NULL){
        ptr01 = ptr01->next;
        ptr02 = ptr02->next;
        if(ptr01 == ptr02){
            printf("\n找到環(huán)的入口點(diǎn):%d\n",ptr02->data);
            return ptr02;
        }
    }
    return NULL;
}

問題3: 環(huán)有多長(zhǎng)

原理:快慢指針第一遍相遇后,然后在進(jìn)行第二遍循,當(dāng)快慢指針再一次相遇時(shí),記錄慢指針走的步數(shù)就是,環(huán)的長(zhǎng)度.

當(dāng)?shù)谝淮蜗嘤龊罅抟牛俅沃匦鲁霭l(fā)署辉，當(dāng)慢指針走了一半時(shí)，此時(shí)快指針已經(jīng)完成了一圈岩四，重新回到出發(fā)點(diǎn)哭尝，當(dāng)慢指針完成一圈時(shí)，快指針正好完成了第二圈剖煌，此時(shí)二者在相同的相遇點(diǎn)完成了第二次相遇材鹦。

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){
            //快慢指針第一次相遇的節(jié)點(diǎn)
            break;
        }
    }
 
     int len = 0;   
 
    while (fast->next != NULL){
        len++;
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){
         //快慢指針第二次相遇的節(jié)點(diǎn)
         return len;
        }
    }
    return 0;
}