一组非负整数,用带头结点的单链表进行存储,定义单键表结点类型,编写算法,求单键表的最大值,并返回该结点的指针。
时间: 2023-05-20 10:01:05 浏览: 52
可以使用以下代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
ListNode* getMaxNode(ListNode* head) {
ListNode* maxNode = head->next;
ListNode* curNode = head->next;
while (curNode != NULL) {
if (curNode->val > maxNode->val) {
maxNode = curNode;
}
curNode = curNode->next;
}
return maxNode;
}
int main() {
// 构造一个带头结点的单链表
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
ListNode* curNode = head;
int nums[] = {1, 5, 3, 9, 2};
int len = sizeof(nums) / sizeof(int);
for (int i = 0; i < len; i++) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = nums[i];
newNode->next = NULL;
curNode->next = newNode;
curNode = newNode;
}
// 求单键表的最大值
ListNode* maxNode = getMaxNode(head);
printf("The max value is %d\n", maxNode->val);
// 释放内存
curNode = head;
while (curNode != NULL) {
ListNode* nextNode = curNode->next;
free(curNode);
curNode = nextNode;
}
return 0;
}
```
这个算法的时间复杂度是 O(n),其中 n 是单键表的长度。