输入样例3 -> 4 -> 7 -> 9 ->12 ->5 ->8,给出一个单链表,不知道节点N的值,怎样只遍历一次就可以求出中间结点。c语言
时间: 2024-05-25 22:17:40 浏览: 31
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode *slow = head, *fast = head;
while (fast && fast->next) { // 快指针每次走两步,慢指针每次走一步
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
相关问题
输入样例3 -> 4 -> 7 -> 9 ->12 ->5 ->8,给出一个单链表,不知道节点N的值,怎样只遍历一次就可以求出中间结点。c语言完整代码
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct ListNode {
int val; // 节点的值
struct ListNode* next; // 指向下一个节点的指针
} ListNode;
// 创建链表
ListNode* createList(int* nums, int size) {
ListNode* dummyHead = (ListNode*)malloc(sizeof(ListNode)); // 创建一个虚拟头结点作为链表的头
dummyHead->next = NULL; // 头结点的next指针指向NULL
ListNode* tail = dummyHead; // tail指针指向虚拟头结点,初始时相当于链表的头结点
for (int i = 0; i < size; i++) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); // 创建一个新的节点
newNode->val = nums[i]; // 新节点的值为nums[i]
newNode->next = NULL; // 新节点的next指针指向NULL
tail->next = newNode; // 将新节点插入到链表的尾部
tail = tail->next; // tail指针向后移动一位,指向新的尾节点
}
return dummyHead->next; // 返回真正的头结点,即虚拟头结点的下一个节点
}
// 找到链表的中间节点
ListNode* findMiddleNode(ListNode* head) {
ListNode* slow = head; // 慢指针指向链表的头
ListNode* fast = head; // 快指针也指向链表的头
while (fast != NULL && fast->next != NULL) { // 当快指针不为NULL且快指针的下一个节点也不为NULL时,循环继续
slow = slow->next; // 慢指针每次向后移动一位
fast = fast->next->next; // 快指针每次向后移动两位
}
return slow; // 当快指针到达链表的末尾时,慢指针正好指向链表的中间节点
}
// 释放链表的内存空间
void freeList(ListNode* head) {
ListNode* p = head; // 定义一个指针p,指向链表的头结点
while (p != NULL) { // 当p不为NULL时,循环继续
ListNode* q = p->next; // 定义一个指针q,指向p的下一个节点
free(p); // 释放p指向的节点的内存空间
p = q; // p指针指向q指针指向的节点
}
}
int main() {
int nums[] = {3, 4, 7, 9, 12, 5, 8}; // 定义一个数组,表示链表的值
int size = sizeof(nums) / sizeof(nums[0]); // 数组的大小
ListNode* head = createList(nums, size); // 创建链表
ListNode* middleNode = findMiddleNode(head); // 找到链表的中间节点
printf("The middle node of the list is %d.\n", middleNode->val); // 输出链表的中间节点的值
freeList(head); // 释放链表的内存空间
return 0;
}
```
给定 N 给出一个单链表,不知道节点N的值,怎样只遍历一次就可以求出中间结点。输入样例:3 -> 4 -> 7 -> 9 ->12 ->5 ->8
解题思路:
快慢指针法,即使用两个指针,一个指针每次走两步,一个指针每次走一步,当快指针走到链表末尾时,慢指针就到了链表的中间。
算法步骤:
1.定义快慢指针,初始化为head节点。
2.循环遍历链表,快指针每次走两步,慢指针每次走一步。
3.当快指针走到链表末尾时,慢指针就到了链表的中间。
4.返回慢指针指向的节点即可。
Python代码实现: