判斷單向鏈表是否有環：快慢指針法（Floyd 判圈算法）

判斷單向鏈表是否有環：快慢指針法

算法原理（Floyd 判圈算法）

1. 設置兩個指針 slow、fast，初始均指向頭結點。
2. slow 每次移動 1 步，fast 每次移動 2 步。
3. 若鏈表**無環**：fast 會先到達末尾（NULL），循環結束，返回無環。
4. 若鏈表**有環**：fast 進入環後，在環內追趕 slow。因相對速度為 1 步/輪，**必定相遇**，返回有環。

完整 C 代碼實現

#include 
#include 
#include 

typedef struct Student {
    int num;
    struct Student *pnext;
} Stu, *PStu;

void link_tail_insert(PStu *phead, PStu *ptail, int val);
void link_show(PStu head);
void link_judge_loop(PStu head);

int main() {
    PStu phead = NULL, ptail = NULL;
    int val;
    while (scanf("%d", &val) != EOF) {
        link_tail_insert(&phead, &ptail, val);
    }
    link_show(phead);
    
    // 人為構造環：尾節點指向頭節點（測試用）
    ptail->pnext = phead;
    
    link_judge_loop(phead);
    return 0;
}

void link_tail_insert(PStu *phead, PStu *ptail, int val) {
    PStu pnew = (PStu)malloc(sizeof(Stu));
    memset(pnew, 0, sizeof(Stu));
    pnew->num = val;
    if (!*ptail) {
        *phead = *ptail = pnew;
    } else {
        (*ptail)->pnext = pnew;
        *ptail = pnew;
    }
}

void link_show(PStu head) {
    PStu p = head;
    if (!head) { puts("empty"); return; }
    while (p) { printf("%d ", p->num); p = p->pnext; }
    putchar('\n');
}

void link_judge_loop(PStu head) {
    PStu slow = head, fast = head;
    while (fast && fast->pnext) {
        slow = slow->pnext;       // 1 步
        fast = fast->pnext->pnext; // 2 步
        if (slow == fast) {
            printf("Link has loop\n");
            return;
        }
    }
    printf("Link has no loop\n");
}

關鍵點解析

• 循環條件：fast && fast->pnext 確保 fast->pnext->pnext 不解引用空指針。
• 相遇證明：環長 L，快慢指針進環後距離 d，每輪縮短 1，最多 L 輪相遇。
• 時間複雜度：O(n)，slow 進環前 O(n)，進環後 O(L) ≤ O(n)。
• 空間複雜度：O(1)，僅兩指針。

進階：找到環入口節點

相遇後，將一指針重置為頭結點，兩指針同速（1 步/輪）前進，**再次相遇點即為環入口**。

PStu find_loop_entry(PStu head) {
    PStu slow = head, fast = head;
    while (fast && fast->pnext) {
        slow = slow->pnext;
        fast = fast->pnext->pnext;
        if (slow == fast) break;
    }
    if (!fast || !fast->pnext) return NULL; // 無環
    slow = head;
    while (slow != fast) {
        slow = slow->pnext;
        fast = fast->pnext;
    }
    return slow; // 環入口
}

總結

快慢指針法是判斷鏈表環的**標準解法**，無需修改節點、無需額外空間、時間線性。掌握「相遇證明、入口查找、鏈表中點查找」三大快慢指針經典應用，是鏈表題必備基本功。