单链表循环检测

• 单链表中的循环

  • 如果链表带循环，从表头开始遍历，最终一定会进入链表循环中使得遍历过程无法适当停止。

• 两质点在同一圆周内的运动

  • 假设两个质点在同一个圆周内沿相同方向作无休止的圆周运动，两质点速度恒定且不相同，则不论初始状态如何，两个质点总有一刻会撞到一起（实际上他们会无数次撞到一起）。

• 代码实现
  根据以上两点，可以写出判断单链表中是否存在循环的代码，如下：

#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;
}