【寻找链表的中间结点】

题目描述 给定一个单链表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 中间结点保存的数据。如果有两个中间结点，则输出第二个中间结点保存的数据。

解析：考察链表知识

代码一：

head, n = input().split()
nodes = {}
for i in range(int(n)):
    curAdd,curVal,nextAdd = input().split()
    nodes[curAdd] = [curVal,nextAdd]
def getVal(head,nodes):
    linknodes = []
    node = nodes.get(head)
    while node[-1] != -1:
        nextAdd = node[-1]
        linknodes.append(node[0])
        node = nodes[nextAdd]
    linknodes.append(node[0])
    mid = int(len(linknodes)/2)
    return linknodes[mid]
print(getVal(head, nodes))

代码二：

head, n = input().split()
nodes = {}
for i in range(int(n)):
    addr, val, nextAddr = input().split()
    nodes[addr] = [val, nextAddr]
 
def getResult(head, nodes):
    linkedlist = []
    node = nodes.get(head)
 
    while node is not None:
        val, next = node
        linkedlist.append(val)
        node = nodes.get(next)
 
    length = len(linkedlist)
    mid = int(length / 2)
 
    return linkedlist[mid]
 
print(getResult(head, nodes))