设计一个算法,通过一趟遍历确定长度为n的单链表中值最大的节点,返回该节点的数据域。 输入样例: n 12 链表值:5 6 7 3 6 8 9 11 13 4 2 0 输出:13 使用c 语言
时间: 2024-09-11 13:17:16 浏览: 15
设计一个算法来找到长度为 `n` 的单链表中最大值的节点,可以采用遍历的方式。以下是使用 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;
}
// 寻找链表的最大值节点
ListNode* findMaxNode(ListNode* head, int n) {
if (head == NULL || n <= 0) {
printf("Invalid input.\n");
return NULL;
}
ListNode* maxNode = head; // 初始最大值节点为头节点
int currMax = head->val; // 当前最大值
for (int i = 1; i < n && head != NULL; i++) {
if (head->val > currMax) { // 如果当前节点值大于已知最大值
maxNode = head;
currMax = head->val;
}
head = head->next; // 遍历下一个节点
}
return maxNode;
}
// 打印链表值
void printList(ListNode* node) {
while (node != NULL) {
printf("%d ", node->val);
node = node->next;
}
printf("\n");
}
int main() {
int n = 12;
ListNode* values[] = {createNode(5), createNode(6), createNode(7), createNode(3),
createNode(6), createNode(8), createNode(9), createNode(11),
createNode(13), createNode(4), createNode(2), createNode(0)};
ListNode* listHead = values[0];
// 连接链表节点
for (int i = 1; i < sizeof(values) / sizeof(values[0]); i++) {
listHead->next = values[i];
listHead = values[i];
}
ListNode* maxValNode = findMaxNode(listHead, n);
if (maxValNode != NULL) {
printf("最大值节点的值: %d\n", maxValNode->val);
} else {
printf("未找到链表节点。\n");
}
return 0;
}
```
当你运行这个程序,它会输出:
```
最大值节点的值: 13
```
这就是找到给定长度链表中最大值节点的数据域的方法。