C语言快慢链表判断链表是否有环
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
typedef struct Node {
int val;
struct Node* next;
}Node, * ListNode;
ListNode LinkListInit();
bool createTail(ListNode L);
bool MakeLoop(ListNode L, int i);
bool hasCycle(ListNode L);
void printLinkList(ListNode L);
ListNode LinkListInit() {
Node* L;
L = (Node*)malloc(sizeof(Node)); //申请结点空间
if (L == NULL) { //判断是否有足够的内存空间
printf("申请内存空间失败\n");
}
L->next = NULL;//将next设置为NULL,初始长度为0的单链表
return L;
}
//输入一个链表的值
bool createTail(ListNode L) {
int x;
Node* s, * r = L;
printf("输入一个链表的值:\n");
scanf("%d", &x);
while (x != 9999) {
s = (Node*)malloc(sizeof(Node));
s->val = x;
r->next = s;
r = s;
scanf("%d", &x);
}
r->next = NULL;
return true;
}
//构造一个带环的链表
bool MakeLoop(ListNode L, int i) {
int j = 1;
ListNode p,q;
Node *s ,* t;//s为特定的结点,t为最后一个结点
p = L->next;
s = NULL;
if (i == 0) {//若i等于0,则返回头结点
return L;
}
if (i < 1) {//若i无效则返回NULL
return NULL;
}
while (p->next != NULL) {
if (j < i) {//找到指定结点时,用s记录位置
s = p;
}
p = p->next;
}
t = p;//跳出while循环时,p已经指向了最后一个结点
//构造循环
t->next = s->next;
return true;
}
//通过快慢指针来判断链表是否有环
bool hasCycle(ListNode L) {
ListNode slow, fast;
slow = L;
fast = L;
while (slow != NULL && fast != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return true;
}
return false;
}
//输出链表
void printLinkList(ListNode L)
{
ListNode p;
p = L->next;
if (p == NULL) {
printf(" ");
}
while (p)
{
printf("%d ", p->val);
p = p->next;
}
printf("\n");
}
int main(void) {
int ch,i;
ListNode L1, L2,R,L;
L1 = LinkListInit();
L2 = LinkListInit();
L = LinkListInit();
R = LinkListInit();
while (1) {
printf("输入0退出程序\n");
printf("输入1创建一个链表\n");
printf("输入2创建一个带环的单链表\n");
printf("输入3判断一个链表是否有环\n");
printf("请选择您要进行的操作:\n");
scanf("%d", &ch);
switch (ch)
{
case 0:
printf("已退出。\n");
exit(0);
break;
case 1:
createTail(L);
break;
case 2:
printf("输入循环链表指向的结点位置。\n");
scanf("%d", &i);
if (MakeLoop(L, i)) {
printf("创建环形链表成功\n");
}
else {
printf("创建环形链表失败\n");
}
break;
case 3:
if (hasCycle(L)) {
printf("true\n");
}
else{
printf("false\n");
}
break;
default: printf("输入的指令有误,请重新输入。\n");
}
}
return 0;
}
hasCycle函数while(slow != NULL && fast !=NULL)时会报错
那为什么写成while(slow != NULL && fast->next != NULL)就没问题啊,快慢指针不是当slow和fast相遇的时候,证明链表有环吗?当slow和fast都不为空时,slow向后移动一位,fast移动两位,当他们相遇的时候即链表有环,若slow和fast为空则无环。
fast != NULL 会报错的原因,因为你循环里面 fast = fast->next->next,指向了下一个节点的下一个节点。