[数据结构与算法]蓝桥杯练习题 自行车停放

自行车停放

问题描述

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

输入格式

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

输出格式

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

样例输入

4
3
1 3 1
2 1 0
5 2 1

样例输出

3 2 5 1

代码

import java.util.Scanner;

public class Main {

    // Java中没有双向链表，需要自己创建
    static class doubleNode
    {
        int data;
        doubleNode prior = null,next = null;
        doubleNode(){

        }
        doubleNode(int data,doubleNode prior,doubleNode next)
        {
            this.data = data;
            this.prior = prior;
            this.next = next;
        }
        doubleNode(int data)
        {
            this.data = data;
            this.prior = this.next = null;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int t = sc.nextInt();
        doubleNode first = new doubleNode(t);
        doubleNode[] loc = new doubleNode[100001];  // 存放地址
        loc[t] = first;
        for(int i=0;i<N-1;i++)
        {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            doubleNode x = new doubleNode(a);
            loc[a] = x;
            doubleNode y = loc[b];
            // x放y左边
            if(c==0)
            {
                // 如果y左边没有结点
                if(y.prior==null)
                {
                    x.prior = null;
                    x.next = y;
                    y.prior = x;
                }
                else
                {
                    y.prior.next = x;
                    x.prior = y.prior;
                    x.next = y;
                    y.prior = x;
                }
            }
            // x放y右边
            else
            {
                // 如果y右边没有结点
                if(y.next ==null)
                {
                    x.next = null;
                    x.prior = y;
                    y.next = x;
                }
                else
                {
                    y.next.prior = x;
                    x.next = y.next;
                    x.prior = y;
                    y.next = x;
                }
            }
        }
        
        
        // 输出
        while (first!=null)
        {
            System.out.print(first.data+" ");
            first = first.next;
        }

    }
}