题目:判断一个单链表中是否有环，如下图:

链表有环

分析:

1. 沿着链表前进，记录已经走过的。每次将新走到的和以前走过的逐一对比。
   时间复杂度O(n^2),额外申请了一倍空间，并且最开始不知道要申请空间的大小，小了得重新申请；大了浪费。
   因此该算法不考虑

2. 第一个指针沿着链表前进，第二个指针每次从头开始。如果两个节点值相等，但是指针一和指针二的步数不同，则有环。
   时间复杂度O(n^2),没有额外空间，可以判断出环的起点

3. 第一个指针以步数2前进，第二个指针以步数1前进。则在环内两者最终会相遇。
   时间复杂度O(n),但是无法判断环的起点。

代码实现:

创建有环列表

typedef struct Node{
    int data;
    struct Node *next;
}Node;
typedef struct Node LinkList;


#define LIST_H

#include "LinkList.h"


LinkList *createList(int n) {
    Node *head = (Node*)malloc(sizeof(Node));
    head->data = 0;
    head->next = NULL;
    Node *currentNode = head;
    for (int i=1; i<=n; i++) {
        Node *node = (Node*)malloc(sizeof(Node));
        node->data = i;
        node->next = NULL;
        currentNode->next = node;
        currentNode = node;
    }
    // 为了模拟有环情况，这里将最后一个节点指向了第三个节点
    currentNode->next = head->next->next->next;
    return head;
}

算法2实现:

int find2(LinkList *list) {
    // 设置current为一直往前走的指针,checker为从头开始循环检查的指针
    Node *current = list, *checker = list;
    // current走的步数
    int step_current = 0;
    // 如果current的下一个节点不为空
    while (current->next != NULL) {
        // current指向下一个节点
        current = current->next;
        // 步数加1
        step_current++;
        // 检查者步数
        int step_checker = 0;
        // 如果检查者下一个节点不为空
        while (checker != NULL) {
            // 如果两个节点相同（这里先判断，后让checker指向下一个是为了环起点就是头节点的情况）
            if (checker == current) {
                // 判断步数是否相同，如果不相同，则有环。否则到目前没有环，checker本次不再检查
                if (step_current != step_checker) {
                    printf("%d\n",checker->data);
                    return 1;
                }
                break;
            }
            // 检查者指向下一个节点
            checker = checker->next;
            // 检查者步数加1
            step_checker++;
        }
        // 检查完一次，checker重新指向头部
        checker = list;
    }
    return 0;
}

算法3实现:

int find3(LinkList *list) {
    Node *step_single = list;
    Node *step_double = list;
    
    while (step_double->next != NULL && step_double->next->next != NULL) {
        step_double = step_double->next->next;
        step_single = step_single->next;
        if (step_single == step_double) {
            printf("%d\n",step_single->data);
            return 1;
        }
    }
    return 0;
}

如果上面有错误，或者您有更好的方法，请在评论区指出。感谢！