当前位置: 首页 > 面试经验 >

【华为OD机试2023】寻找链表的中间结点(Python)

优质
小牛编辑
138浏览
2023-03-28

【华为OD机试2023】寻找链表的中间结点(Python)

题目描述:

给定一个单链表 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 情况 。

示例1

输入:

00100 4

00000 4 -1

00100 1 12309

33218 3 00000

12309 2 33218

输出:

3

示例2

输入:

10000 3

76892 7 12309

12309 5 -1

10000 1 76892

输出:

7

解题思路:

用两个字典存储


#单字典存储
start,n=input().split()
target=int(n)//2+1
lianbiao={}
for i in range(int(n)):
data=input().split()
lianbiao[data[0]]=[data[1],data[2]]

count=0
num=0
while count<target:
num = lianbiao[start][0]
start=lianbiao[start][1]
count+=1
print(num)



#双字典存储
start,n=input().split()
n=int(n)
#存储address和next的字典
x={}
#存储address和data的字典
y={}
s=[input().split() for i in range(n)]
count=2
end=n//2+1
for item in s:
x[item[0]]=item[2]
y[item[0]]=item[1]
key=x[start]
while count<end:
key=x[key]
count+=1
print(y[key])

#华为机试,emo了#
 类似资料: