给出一个单链表,不知道结点n的值,遍历一次求出中间结点c语言
时间: 2023-04-19 22:00:49 浏览: 67
假设单链表的头结点为head,可以使用快慢指针的方法来求出中间结点。
定义两个指针slow和fast,初始时都指向头结点head。每次循环时,slow指针向后移动一个结点,fast指针向后移动两个结点。当fast指针到达链表末尾时,slow指针所指的结点就是中间结点。
具体实现代码如下:
```
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* middleNode(struct ListNode* head){
struct ListNode *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
```
其中,slow指针每次移动一个结点,fast指针每次移动两个结点,因此时间复杂度为O(n/2),空间复杂度为O(1)。
相关问题
用c语言写出一个算法,通过一趟遍历在单链表中确定值最大的结点
好的,这个问题我可以回答。以下是用 C 语言写出的算法:
```c
#include <stdio.h>
#include <stdlib.h>
struct Node {
int val;
struct Node *next;
};
struct Node *findMaxNode(struct Node *head) {
struct Node *maxNode = head;
struct Node *curNode = head->next;
while (curNode != NULL) {
if (curNode->val > maxNode->val) {
maxNode = curNode;
}
curNode = curNode->next;
}
return maxNode;
}
int main() {
// 构造一个单链表
struct Node *head = (struct Node *)malloc(sizeof(struct Node));
head->val = 1;
head->next = NULL;
struct Node *curNode = head;
for (int i = 2; i <= 10; i++) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->val = i;
newNode->next = NULL;
curNode->next = newNode;
curNode = newNode;
}
// 找到值最大的结点
struct Node *maxNode = findMaxNode(head);
printf("值最大的结点的值为:%d\n", maxNode->val);
// 释放内存
curNode = head;
while (curNode != NULL) {
struct Node *nextNode = curNode->next;
free(curNode);
curNode = nextNode;
}
return 0;
}
```
这个算法的思路是,从头结点开始遍历单链表,用一个指针记录当前值最大的结点,如果遇到比当前值最大的结点的值更大的结点,就更新指针。遍历完成后,指针所指向的结点就是值最大的结点。
输入样例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;
}
```