c语言判断链表是否有环

1.问题描述

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

数据范围：链表长度 ，链表中任意节点的值满足

要求：空间复杂度 ，时间复杂度

2.基本原理

起初，快指针和慢指针一起指向头节点。快指针每次走2步，慢指针每次走1布，直到走到尾节点。若快指针与慢指针相遇，则说明链表中有环；若不相遇，则说明链表中无环。

3.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

typedef struct ListNode ListNode;

struct ListNode {
    int val;
    struct ListNode *next;
};

void ListPush(ListNode **head, int val)
{
    ListNode *pre = NULL;
    ListNode *cur = (*head);

    if(cur == NULL)
    {
        *head = (ListNode *)malloc(sizeof(ListNode));

        (*head)->val = val;
        (*head)->next = NULL;

        return;
    }

    while(cur)
    {
        pre = cur;
        cur = cur->next;
    }

    cur = (ListNode *)malloc(sizeof(ListNode));

    pre->next = cur;
    cur->val = val;
    cur->next = NULL;

    return;
}

void ListFree(ListNode **head)
{
    ListNode *next = NULL;
    ListNode *cur = (*head);

    while(cur)
    {
        next = cur->next;

        free(cur);

        cur = next;
    }

    *head = NULL;
}

void ListPrint(ListNode *head)
{
    ListNode *cur = head;

    while(cur)
    {
        printf("%d ", cur->val);

        cur = cur->next;
    }

    printf("\n");
}

short hasCycle(struct ListNode *head)
{
    struct ListNode *p = head;
    struct ListNode *q = head;
    short res = 0;

    while(1)
    {
        if(p == NULL)
        {
            break;
        }

        p = p->next;

        if(p == NULL)
        {
            break;
        }

        p = p->next;
        q = q->next;

        if(p == q)
        {
            res = 1;
            break;
        }
    }

    return res;
}

int main()
{
    ListNode *head = NULL;

    ListPush(&head, 1);
    ListPush(&head, 4);
    ListPush(&head, 5);

    printf("%d\n", hasCycle(head));

    ListFree(&head);

    return 0;
}

4.编译源码

$ gcc -o test test.c -std=c89

5.运行及其结果

$ ./test
0