编写一个函数，判断链表中是否有环

使用快慢指针法，快指针每次走两步，慢指针每次走一步，如果存在环，快指针最终会追上慢指针，否则快指针会先到达链表尾部。

Python代码实现如下：

def hasCycle(head):
    if not head or not head.next:
        return False
    slow, fast = head, head.next
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    return True

时间复杂度为O(n)，空间复杂度为O(1)。

相关问题

C编写一个函数，判断链表中是否有环

以下是一种基于快慢指针的方法来判断链表中是否有环。

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

bool hasCycle(ListNode *head) {
    // 如果链表为空或只有一个节点，则一定没有环
    if (!head || !head->next) {
        return false;
    }
    // 定义快慢指针
    ListNode *slow = head;
    ListNode *fast = head->next;
    // 当快指针能够继续向前，且慢指针没有追上快指针时
    while (fast && fast->next && slow != fast) {
        slow = slow->next;
        fast = fast->next->next;
    }
    // 如果快指针已经到达链表末尾，说明链表没有环
    if (!fast || !fast->next) {
        return false;
    }
    // 如果慢指针追上了快指针，说明链表有环
    return true;
}

该函数的基本思路是，使用两个指针slow和fast，开始时它们都指向链表的头部。slow每次向后移动一个节点，而fast每次向后移动两个节点。如果链表中有环，那么fast指针一定会在某个时刻追上slow指针。如果链表中没有环，那么fast指针会在到达链表末尾之前先到达NULL节点。

C语言编写一个函数，判断链表中是否有环

以下是一个判断链表中是否有环的C语言函数：

#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            return true;
        }
    }
    
    return false;
}

这个函数使用快慢指针的方法来判断链表中是否有环。初始时，将慢指针和快指针都指向链表头部。然后，慢指针一次移动一个节点，快指针一次移动两个节点。如果链表中有环，那么快指针最终会追上慢指针，两个指针会相遇。如果链表中没有环，那么快指针会先到达链表尾部，此时循环结束。

因此，可以根据快慢指针的相对位置来判断链表中是否有环。如果两个指针相遇，则说明链表中有环；否则，说明链表中没有环。