C语言求单链表中间结点值（单链表长度随机、求解速度越快越好）

题目描述

求单链表中间结点值。（单链表长度随机、求解速度越快越好）

要求

1、根据题目要求，阐明解决问题的基本思路，大致预估一下所选策略的求解效率。

2、简要写出算法的实现步骤(形式语言即可），并附上相应流程图图片。

3、算法实现

（1）选择c语言编程实现，并附上运行界面和运行结果的图片。

（2）根据运行结果，说明算法实现后其求解效率是否达到预期。

（3）附上程序源代码

解决思路

基本思路及效率预估： 我们可以利用快慢指针的方法来求解单链表中间节点值。具体做法是定义两个指针，一个每次移动一步，另一个每次移动两步，直到快指针到达链表尾部时，慢指针所指向的位置即为中间节点。这种方法的时间复杂度为 O(n/2)，其中 n 是链表的长度。由于只需遍历一次链表，因此效率较高。

算法实现步骤：

1. 定义两个指针 slow 和 fast，初始时都指向链表的头节点。
2. 使用循环，每次让 slow 指针向后移动一步，fast 指针向后移动两步，直到 fast 指针到达链表尾部。
3. 此时 slow 指针所指向的位置即为中间节点。

源代码

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

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

struct Node* findMiddle(struct Node* head) {
    struct Node *slow = head, *fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

int main() {
    // 创建链表
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = NULL;
    struct Node* current = head;

    for (int i = 2; i <= 10; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = i;
        newNode->next = NULL;
        current->next = newNode;
        current = newNode;
    }

    // 寻找中间节点
    struct Node* middle = findMiddle(head);
    printf("中间节点的值为：%d\n", middle->data);

    return 0;
}

运行截图