-
單鏈表中的循環(huán)
- 如果鏈表帶循環(huán)狞玛，從表頭開始遍歷，最終一定會進(jìn)入鏈表循環(huán)中使得遍歷過程無法適當(dāng)停止涧窒。
-
兩質(zhì)點(diǎn)在同一圓周內(nèi)的運(yùn)動
- 假設(shè)兩個質(zhì)點(diǎn)在同一個圓周內(nèi)沿相同方向作無休止的圓周運(yùn)動心肪，兩質(zhì)點(diǎn)速度恒定且不相同，則不論初始狀態(tài)如何纠吴，兩個質(zhì)點(diǎn)總有一刻會撞到一起（實(shí)際上他們會無數(shù)次撞到一起）硬鞍。
代碼實(shí)現(xiàn)
根據(jù)以上兩點(diǎn)，可以寫出判斷單鏈表中是否存在循環(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;
}
