一、题目描述
给定一个单链表 L，请编写程序输出 L中间结点保存的数据。如果有两个中间结点，则输出第二个中间结点保存的数据。
例如：
给定 L 为 1 -> 7 -> 5，则输出应该为 7; 给定 L 为 1 -> 2 -> 3 -> 4，则输出应该为 3。
二、输入描述
每个输入包含 1 个测试用例。每个测试用例第 1行给出链表首结点的地址、结点总个数正整数 N(<=105)。结点的地址是 5位非负整数，
NULL 地址用-1表示 。
接下来有 N 行，每行格式为:
Address Data Next
其中 Address 是结点地址，Data 是该结点保存的整数数据(0<=Data<=108)，Next是下一结点的地址。
三、输出描述
对每个测试用例，在一行中输出L 中间结点保存的数据。如果有两个中间结点，则输出第二个中间结点保存的数据。
四、补充说明
已确保输入的结点所构成的链表L不会成环，但会存在部分输入结点不属于链表L情况。
五、解题思路
- 读取输入的链表首结点地址和结点总个数；
- 根据结点总个数计算出中间结点的索引 index，如果结点总个数为偶数，则取第二个中间结点；
- 创建一个哈希表 map，用于存储每个结点的地址和对应的数据和下一结点的地址；
- 遍历输入的结点信息，将每个结点的地址作为键，整个结点信息作为值存储到哈希表 map 中；
- 根据给定的首结点地址，找到对应的结点信息；
- 遍历链表，从首结点开始依次获取下一结点的地址，并根据地址在哈希表 map 中查找对应的结点信息；
- 当遍历到中间结点时，输出该结点保存的数据；
六、Python算法源码
def get_middle_node(data):
lines = data.split("\n")
first_line = lines[0].split(" ")
addr = first_line[0]
length = int(first_line[1])
index = length // 2
node_map = {}
for i in range(1, length + 1):
node = lines[i].split(" ")
node_map[node[0]] = node
pre_node = node_map[addr]
for i in range(1, length):
next_addr = pre_node[2]
nodes = node_map[next_addr]
if i == index:
return nodes[1]
pre_node = nodes
七、效果展示
1、输入
1 4
2 1 -1
1 2 4
3 3 2
4 4 3
2、输出
3
🏆下一篇：华为OD机试真题 Python 实现【相对开音节】【2022Q4 100分】，附详细解题思路
🏆本文收录于，华为OD机试（Python）真题（A卷+B卷）
每一题都有详细的答题思路、详细的代码注释、样例测试，订阅后，专栏内的文章都可看，可加入华为OD刷题群（私信即可），发现新题目，随时更新，全天CSDN在线答疑。