华为OD机试 - 单向链表中间节点（Python/JS/C/C++ 2024 E卷 200分）

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

求单向链表中间的节点值，如果奇数个节点取中间，偶数个取偏右边的那个值。

二、输入描述

第一行链表头节点地址后续输入的节点数 n
后续输入每行表示一个节点，格式：节点地址节点值节点地址下一个节点地址（-1 表示空指针 Q）

输入保证链表不会出现环，并且可能存在一些节点不属于链表。

三、输出描述

单向链表中间的节点值

四、测试用例

测试用例1：

1、输入

00010 4
00000 3 -1
00010 5 12309
11451 6 00000
12309 7 11451

2、输出

3、说明

链表顺序为：00010 (5) -> 12309 (7) -> 11451 (6) -> 00000 (3)
总节点数为 4，偶数，取第 3 个节点的值为 6。

测试用例2：

1、输入

10000 3
76892 7 12309
12309 5 -1
10000 1 76892

2、输出

3、说明

链表顺序为：10000 (1) -> 76892 (7) -> 12309 (5)
总节点数为 3，奇数，取第 2 个节点的值为 7。

五、解题思路

输入读取：
- 使用 Scanner 从标准输入读取链表的头节点地址和节点总数 n。
- 读取接下来的 n 行，每行包含一个节点的地址、值和下一个节点的地址。
- 使用 HashMap<String, Node> 将节点地址映射到对应的 Node 对象，便于快速查找节点。
链表遍历：
- 从头节点地址开始，依次通过 next 地址遍历链表。
- 将遍历到的每个节点的值存储在 List nodeValues 中。
- 如果遇到地址为 -1，表示链表结束；或者当前地址在 HashMap 中不存在，表示链表异常结束。
中间节点查找：
- 根据链表长度 size 计算中间节点的索引 middleIndex。
- 对于奇数个节点，middleIndex = size / 2，例如 5 个节点，索引为 2。
- 对于偶数个节点，middleIndex = size / 2，例如 4 个节点，索引为 2（偏右）。
- 输出中间节点的值。
辅助类：
- Node 类用于表示链表中的每个节点，包含地址、值和下一个节点的地址。

六、Python算法源码

# 导入所需的模块
import sysdef main():# 读取输入input = sys.stdin.read().split()idx = 0# 读取链表头节点地址和节点总数 nhead_address = input[idx]idx += 1n = int(input[idx])idx += 1# 使用字典存储所有节点的信息，键为节点地址，值为（值, 下一个节点地址）node_map = {}for _ in range(n):address = input[idx]idx += 1value = int(input[idx])idx += 1next_address = input[idx]idx += 1node_map[address] = (value, next_address)# 遍历链表，按顺序收集节点的值node_values = []current_address = head_addresswhile current_address != "-1":if current_address not in node_map:# 如果当前地址不存在于 node_map 中，链表结束breakcurrent_node = node_map[current_address]node_values.append(current_node[0])current_address = current_node[1]# 判断链表是否为空if not node_values:print("链表为空。")else:# 计算中间节点的索引size = len(node_values)middle_index = size // 2  # 对于偶数，取偏右边的节点print(node_values[middle_index])if __name__ == "__main__":main()

七、JavaScript算法源码

// 定义节点类，表示链表中的每个节点
class Node {constructor(address, value, next) {this.address = address; // 节点地址this.value = value;     // 节点值this.next = next;       // 下一个节点的地址}
}// 主函数
function main() {const fs = require('fs');const input = fs.readFileSync('/dev/stdin').toString().trim().split(/\s+/);let idx = 0;// 读取链表头节点地址和节点总数 nconst headAddress = input[idx++];const n = parseInt(input[idx++]);// 使用对象存储所有节点的信息，键为节点地址，值为 Node 对象const nodeMap = {};for (let i = 0; i < n; i++) {const address = input[idx++];const value = parseInt(input[idx++]);const next = input[idx++];nodeMap[address] = new Node(address, value, next);}// 遍历链表，按顺序收集节点的值const nodeValues = [];let currentAddress = headAddress;while (currentAddress !== "-1") {if (!(currentAddress in nodeMap)) {// 如果当前地址不存在于 nodeMap 中，链表结束break;}const currentNode = nodeMap[currentAddress];nodeValues.push(currentNode.value);currentAddress = currentNode.next;}// 判断链表是否为空if (nodeValues.length === 0) {console.log("链表为空。");} else {// 计算中间节点的索引const size = nodeValues.length;const middleIndex = Math.floor(size / 2); // 对于偶数，取偏右边的节点console.log(nodeValues[middleIndex]);}
}// 执行主函数
main();

八、C算法源码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>// 定义最大地址长度
#define MAX_ADDR_LEN 20// 定义节点结构体
typedef struct Node {char address[MAX_ADDR_LEN]; // 节点地址int value;                   // 节点值char next[MAX_ADDR_LEN];    // 下一个节点的地址
} Node;// 主函数
int main() {char headAddress[MAX_ADDR_LEN];int n;// 读取链表头节点地址和节点总数 nscanf("%s %d", headAddress, &n);// 使用数组存储所有节点的信息Node *nodeMap = (Node *)malloc(n * sizeof(Node));for (int i = 0; i < n; i++) {scanf("%s %d %s", nodeMap[i].address, &nodeMap[i].value, nodeMap[i].next);}// 遍历链表，按顺序收集节点的值int *nodeValues = (int *)malloc(n * sizeof(int));int count = 0;char currentAddress[MAX_ADDR_LEN];strcpy(currentAddress, headAddress);while (strcmp(currentAddress, "-1") != 0) {int found = 0;for (int i = 0; i < n; i++) {if (strcmp(nodeMap[i].address, currentAddress) == 0) {nodeValues[count++] = nodeMap[i].value;strcpy(currentAddress, nodeMap[i].next);found = 1;break;}}if (!found) {// 如果当前地址不存在于 nodeMap 中，链表结束break;}}// 判断链表是否为空if (count == 0) {printf("链表为空。\n");} else {// 计算中间节点的索引int middleIndex = count / 2; // 对于偶数，取偏右边的节点printf("%d\n", nodeValues[middleIndex]);}// 释放动态分配的内存free(nodeMap);free(nodeValues);return 0;
}

九、C++算法源码

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>using namespace std;// 定义节点结构体
struct Node {string address; // 节点地址int value;      // 节点值string next;    // 下一个节点的地址
};int main() {string headAddress;int n;// 读取链表头节点地址和节点总数 ncin >> headAddress >> n;// 使用无序映射存储所有节点的信息，键为节点地址，值为 Node 结构体unordered_map<string, Node> nodeMap;for (int i = 0; i < n; ++i) {string address, next;int value;cin >> address >> value >> next;nodeMap[address] = Node{address, value, next};}// 遍历链表，按顺序收集节点的值vector<int> nodeValues;string currentAddress = headAddress;while (currentAddress != "-1") {if (nodeMap.find(currentAddress) == nodeMap.end()) {// 如果当前地址不存在于 nodeMap 中，链表结束break;}Node currentNode = nodeMap[currentAddress];nodeValues.push_back(currentNode.value);currentAddress = currentNode.next;}// 判断链表是否为空if (nodeValues.empty()) {cout << "链表为空。" << endl;} else {// 计算中间节点的索引int size = nodeValues.size();int middleIndex = size / 2; // 对于偶数，取偏右边的节点cout << nodeValues[middleIndex] << endl;}return 0;
}