c - C语言快慢链表,这样实现为什么不行?
问题描述:
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为空则无环。
第 1 个答案:
fast != NULL 会报错的原因,因为你循环里面 fast = fast->next->next,指向了下一个节点的下一个节点。
/Users/yangqing/demo2/vision_serve/node_modules/cores/lib/c ...