感谢微信好友——不知火yyds大佬的帮助

题目描述

有 nn 辆自行车依次来到停车棚，除了第一辆自行车外，每辆自行车都会恰好停放在已经在停车棚里的某辆自行车的左边或右边。(e.g.停车棚里已经有 33 辆自行车，从左到右编号为：3,5,13,5,1。现在编号为 22 的第 44 辆自行车要停在 55 号自行车的左边，所以现在停车棚里的自行车编号是：3,2,5,13,2,5,1)。给定nn辆自行车的停放情况，按顺序输出最后停车棚里的自行车编号。n\leq 100000n≤100000。

输入描述

第一行一个整数 nn。 第二行一个整数xx。表示第一辆自行车的编号。 以下 n-1n−1 行，每行 33 个整数 x,y,zx,y,z。 z=0z=0 时，表示编号为 xx 的自行车恰停放在编号为 yy 的自行车的左边。 z=1z=1 时，表示编号为 xx 的自行车恰停放在编号为 yy 的自行车的右边。

输出描述

从左到右输出停车棚里的自行车编号

输入输出样例

示例

输入

4
3
1 3 1
2 1 0
5 2 1

输出

3 2 5 1

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

代码：

n = int(input())
#创建节点类
class LinkList():
    def __init__(self,data):
        self.data = data
        self.pre = None
        self.next = None
#创建字典，用于找到每一个数对应的位置
local = {}
#创建头节点
m = int(input())
node = LinkList(m)
head = node
local[m] = node
#插入n-1个节点
for i in range(1,n):
    a,b,c = map(int,input().split())
    node = LinkList(a)
    #c=1，a插入b右边
    if c == 1:
        #判断b右边是否为空，不为空则将插入节点与后面的节点连接
        if local[b].next:
            local[b].next.pre = node
            node.next = local[b].next
        local[b].next = node
        node.pre = local[b]
    #c=0,a插入b左边
    else:
        #判断b左边是否为空，不为空则将插入节点与前面的节点连接，为空则插入后标注为头节点
        if not local[b].pre:
            local[b].pre = node
            node.next = local[b]
            head = node
        else:
            local[b].pre.next = node
            node.pre = local[b].pre
            local[b].pre = node
            node.next = local[b]
    #记录a的位置
    local[a] = node
#打印输出
while head:
    print(head.data,end = ' ')
    head = head.next