题目:判断一个单链表中是否有环，如下图:
链表有环
分析:
沿着链表前进，记录已经走过的。每次将新走到的和以前走过的逐一对比。
时间复杂度O(n^2),额外申请了一倍空间，并且最开始不知道要申请空间的大小，小了得重新申请；大了浪费。
因此该算法不考虑第一个指针沿着链表前进，第二个指针每次从头开始。如果两个节点值相等，但是指针一和指针二的步数不同，则有环。
时间复杂度O(n^2),没有额外空间，可以判断出环的起点第一个指针以步数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;
}
如果上面有错误，或者您有更好的方法，请在评论区指出。感谢！
