感谢微信好友——不知火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 的自行车的右边。
输出描述
从左到右输出停车棚里的自行车编号
输入输出样例
示例
输入
1. 4 2. 3 3. 1 3 1 4. 2 1 0 5. 5 2 1
输出
3 2 5 1
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
代码：
1. n = int(input()) 2. #创建节点类 3. class LinkList(): 4. def __init__(self,data): 5. self.data = data 6. self.pre = None 7. self.next = None 8. #创建字典，用于找到每一个数对应的位置 9. local = {} 10. #创建头节点 11. m = int(input()) 12. node = LinkList(m) 13. head = node 14. local[m] = node 15. #插入n-1个节点 16. for i in range(1,n): 17. a,b,c = map(int,input().split()) 18. node = LinkList(a) 19. #c=1，a插入b右边 20. if c == 1: 21. #判断b右边是否为空，不为空则将插入节点与后面的节点连接 22. if local[b].next: 23. local[b].next.pre = node 24. node.next = local[b].next 25. local[b].next = node 26. node.pre = local[b] 27. #c=0,a插入b左边 28. else: 29. #判断b左边是否为空，不为空则将插入节点与前面的节点连接，为空则插入后标注为头节点 30. if not local[b].pre: 31. local[b].pre = node 32. node.next = local[b] 33. head = node 34. else: 35. local[b].pre.next = node 36. node.pre = local[b].pre 37. local[b].pre = node 38. node.next = local[b] 39. #记录a的位置 40. local[a] = node 41. #打印输出 42. while head: 43. print(head.data,end = ' ') 44. head = head.next
