设计一个算法,通过一趟遍历确定长度为n的单链表中值最大的节点,返回该节点的数据域。 输入样例: n 12 链表值:5 6 7 3 6 8 9 11 13 4 2 0 输出:13 用c语言编程
时间: 2024-09-11 12:17:27 浏览: 44
算法描述如下:
1. 初始化两个指针,一个是头指针`head`,指向链表的第一个节点;另一个是遍历指针`current`,也指向链表的第一个节点。
2. 初始化一个变量`maxValue`用于记录遇到的最大值,初始时可以设置为链表的第一个节点的值。
3. 通过遍历指针`current`,从头到尾遍历链表中的所有节点。
4. 在遍历过程中,比较`current`指向的节点的值与`maxValue`,如果`current`指向的节点的值更大,则更新`maxValue`为该节点的值。
5. 遍历完成后,`maxValue`中存储的就是链表中的最大值。
6. 返回`maxValue`。
下面是用C语言实现该算法的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 创建链表节点的函数
ListNode* createNode(int val) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 查找链表中最大值的函数
int findMaxValue(ListNode* head) {
if (head == NULL) {
return -1; // 如果链表为空,返回-1或其他错误码
}
int maxValue = head->val;
ListNode* current = head->next;
while (current != NULL) {
if (current->val > maxValue) {
maxValue = current->val;
}
current = current->next;
}
return maxValue;
}
// 打印链表的函数(用于测试)
void printList(ListNode* head) {
ListNode* current = head;
while (current != NULL) {
printf("%d ", current->val);
current = current->next;
}
printf("\n");
}
int main() {
// 创建链表
ListNode* head = createNode(5);
head->next = createNode(6);
head->next->next = createNode(7);
head->next->next->next = createNode(3);
head->next->next->next->next = createNode(6);
head->next->next->next->next->next = createNode(8);
head->next->next->next->next->next->next = createNode(9);
head->next->next->next->next->next->next->next = createNode(11);
head->next->next->next->next->next->next->next->next = createNode(13);
head->next->next->next->next->next->next->next->next->next = createNode(4);
head->next->next->next->next->next->next->next->next->next->next = createNode(2);
head->next->next->next->next->next->next->next->next->next->next->next = createNode(0);
// 打印链表
printf("链表值:");
printList(head);
// 查找最大值
int maxValue = findMaxValue(head);
printf("输出:%d\n", maxValue);
// 清理链表内存
ListNode* current = head;
while (current != NULL) {
ListNode* toDelete = current;
current = current->next;
free(toDelete);
}
return 0;
}
```
阅读全文