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.4k
1 个回答

fast != NULL 会报错的原因,因为你循环里面 fast = fast->next->next,指向了下一个节点的下一个节点。

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题
logo
Microsoft
子站问答
访问
宣传栏