单链表中的爹题

题目描述：给定两个可能有环也可能无环的单链表，头结点head1和head2，请实现一个函数，如果两个链表相交，请返回相交的第一个结点，如果不相交，返回null

解决代码：

#include <stdio.h>
#include <stdbool.h>

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

struct ListNode* detectCycle(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return NULL; // 链表为空或只有一个节点，不可能有环
    }

    struct ListNode* slow = head;
    struct ListNode* fast = head;

    // 快慢指针相遇的检测
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            break; // 快慢指针相遇，说明链表有环
        }
    }

    // 如果快指针到达链表末尾，说明链表无环
    if (fast == NULL || fast->next == NULL) {
        return NULL;
    }

    // 将慢指针重新指向链表头部
    slow = head;

    // 在相遇点和头节点分别设置一个新指针，每次移动一步，它们相遇的节点即为环的入口
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}

// 示例用法
int main() {
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = 1;
    head->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->val = 2;
    head->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->next->val = 3;
    head->next->next->next = head->next;  // 创建一个环

    struct ListNode* result = detectCycle(head);

    if (result != NULL) {
        printf("The linked list has a cycle, and the entrance to the cycle is at node with value %d.\n", result->val);
    } else {
        printf("The linked list does not have a cycle.\n");
    }

    // 释放内存
    while (head != NULL) {
        struct ListNode* temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}