题目描述
给定一个单链表L,请编写程序输出L中间节点保存的数据。
如果有两个中间节点,则输出第二个中间节点保存的数据。
例如:
给定L为1→7→5,则输出应该为7;
给定L为1→2→3→4,则输出应该为3.
输入格式
每个输入包含1个测试用例。每个测试用例第一行给出链表首节点的地址、节点总个数为正整数N (N≤105)。
节点的地址是5位非负整数,NULL地址用-1表示。
接下来有N行,每行格式为:
Address Data Next
其中Adress是节点地址,Data是该节点保存的 整数数据,Next是下一个节点的地址。
以确保输入的节点所构成的链表L不会成环,但会存在部分输入节点不属于链表L的情况
输出格式
对每个测试用例,在一行中输出L中间节点保存的数据。
如果有两个中间节点,则输出第二个中间节点保存的数据。、
输入样例
00100 4
00000 4 -1
00100 1 12309
33218 3 00000
12309 2 33218
输出样例
3
题解思路
根据输入的地址、数据、下一节点地址将数据保存在哈表中。
哈希表的 key 是地址,值是一个包含两个元素的列表,第一个元素为该节点的值,第二个元素为他的后继节点。
新建一个列表,用来按顺序保存链表。根据输入的头结点,遍历链表,并把数据按准许存入列表。
列表中间位置的数字就是答案。
代码
import sys
from collections import defaultdict
# 处理输入
for line in sys.stdin:
a.append(list(map(int, line.split())))
# a 中第一行保存的是头结点和节点个数
head = a[0][0]
#哈希表保存链表
h = defaultdict(list)
# 遍历输入数据,构造链表
for node in a:
h[node[0]].append(node[1])
h[node[0]].append(node[2])
# 新建列表,用来按顺序保存所有数据
b = []
# 遍历链表,把数据保存的 b 列表中
p = head
while p != -1:
b.append(h[p][0])
p = h[p][1]
# 列表中间的那个数就是答案
print(b[len(b) // 2])
版权声明:本文为u014339447原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。