给定一个头结点为head的非空单链表,返回链表的中间结点。如果有两个中间节点,则返回第二个中间结点。C语言程序为
时间: 2024-08-12 16:07:14 浏览: 51
50.两个链表的第一个公共节点1
在C语言中,我们可以使用快慢指针的方法来解决这个问题。快指针每次移动两步,慢指针每次移动一步,这样当快指针到达链表的末尾时,慢指针正好在链表的中间位置(如果有两个中间节点,慢指针会停在第二个中间节点)。下面是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 返回链表的中间节点
ListNode* findMiddleNode(ListNode* head) {
if (head == NULL) return NULL;
// 初始化两个指针,初始时快指针和慢指针都指向头节点
ListNode* fast = head;
ListNode* slow = head;
// 快慢指针同时移动
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next; // 快指针前进两步
slow = slow->next; // 慢指针前进一步
}
return slow; // 返回慢指针所指的节点,即链表的中间节点
}
// 测试函数
void printList(ListNode* head) {
while (head) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
int main() {
// 创建一个测试链表,例如: 1 -> 2 -> 3 -> 4 -> 5
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
head->val = 1;
head->next = (ListNode*)malloc(sizeof(ListNode));
head->next->val = 2;
head->next->next = (ListNode*)malloc(sizeof(ListNode));
head->next->next->val = 3;
head->next->next->next = (ListNode*)malloc(sizeof(ListNode));
head->next->next->next->val = 4;
head->next->next->next->next = (ListNode*)malloc(sizeof(ListNode));
head->next->next->next->next->val = 5;
head->next->next->next->next->next = NULL;
printf("Original List: ");
printList(head);
// 找到并打印中间节点
ListNode* middleNode = findMiddleNode(head);
printf("Middle Node: %d\n", middleNode->val);
free(middleNode);
return 0;
}
```
阅读全文