• 單鏈表中的循環(huán)

  • 如果鏈表帶循環(huán)，從表頭開始遍歷，最終一定會進(jìn)入鏈表循環(huán)中使得遍歷過程無法適當(dāng)停止。

• 兩質(zhì)點在同一圓周內(nèi)的運動

  • 假設(shè)兩個質(zhì)點在同一個圓周內(nèi)沿相同方向作無休止的圓周運動，兩質(zhì)點速度恒定且不相同，則不論初始狀態(tài)如何，兩個質(zhì)點總有一刻會撞到一起（實際上他們會無數(shù)次撞到一起）。

• 代碼實現(xiàn)
  根據(jù)以上兩點，可以寫出判斷單鏈表中是否存在循環(huán)的代碼，如下：

#include <stdio.h>

typedef struct node {
    struct node *next;
    int data;
} node_t;

int check_cycle(node_t *list)
{
    node_t *a = list, *b = list;

    while (b) {
        a = a->next;
        b = b->next;        

        if (!b) {
            break;
        }

        b = b->next;

        if (b == a) {
            return 1;
        }
    }

    return 0;
}

int main()
{
    int i;
    node_t list[100];

    for (i = 0; i < 100; i++) {
        list[i].next = &list[i+1];
    }

    list[99].next = &list[50];
    if (check_cycle(list)) {
        printf("list cycle detected!\n");
    } else {
        printf("list ok!\n");
    }

    list[99].next = NULL;
    if (check_cycle(list)) {
        printf("list cycle detected!\n");
    } else {
        printf("list ok!\n");
    }

    return 0;
}