已知带头节点的单链表,设计一个算法(C函数),查找链表的中间位置的节点,并返回该节点的指针,要求只能遍历一次。
时间: 2024-11-15 10:20:03 浏览: 5
在C语言中,你可以通过迭代的方式来找到单链表的中间节点。这里是一个简单的算法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 仅遍历一次链表获取中间节点的指针
Node* findMiddle(Node* head) {
if (head == NULL || head->next == NULL) { // 如果链表为空或只有一个元素
return head;
}
Node* slow = head; // 使用慢指针,每次移动一步
Node* fast = head; // 使用快指针,每次移动两步
while (fast != NULL && fast->next != NULL) { // 当快指针未到达链表末尾时
slow = slow->next; // 慢指针前进一步
fast = fast->next->next; // 快指针前进两步
}
return slow; // 返回慢指针,此时它指向的就是链表的中间节点
}
int main() {
// 示例链表
Node* list = createLinkedList(); // 创建链表函数自行实现
Node* middle = findMiddle(list);
printf("Middle node value: %d\n", middle->data);
freeList(list); // 清理链表
return 0;
}
```
在这个`findMiddle`函数中,我们利用了两个指针策略,当快指针到达链表尾部时,慢指针正好位于中间。注意这个算法假设链表长度为偶数,如果长度为奇数,慢指针将停在最后一个中间节点。
阅读全文