学步园

链表，头尾指针都是类，node类自引用
移动小球

描述

给你n个小球，从左到右编号依次为1,2,3,4,5,6.........n，并规定小球1的左边的球号为n，小球n的右边的球号为1.现在有以下3种操作：A x y表示把编号为x小球移动到编号为y的小球的左边，B x y表示把编号为x小球移动到编号为y的小球的右边，Q 1 m为询问编号为m的小球右边的球号，Q 0 m为询问编号为m的小球左边的球号。

输入

第一行有一个整数n(0<n<10000),表示有n组测试数据，随后每一组测试数据第一行是两个整数N,M，其中N表示球的个数(1<N<10000)，M表示操作的的次数(0<M<10000)
随后的M行，每行有三个数 s x y，s表示操作的类型，x，y为小球号。当s为Q时，若x为1，则询问小球y右边的球号，x为0，则询问小球y左边的球号。

输出

输出每次询问的球号

样例输入

1
6 3
A 1 4
B 3 5
Q 1 5

样例输出

            3

 
import java.util.Scanner;
class node
{
	int num;
	node forenoNode;
	node nextNode;
	public node(int num,node pNode,node nnode) {
	  this.num=num;
	  this.forenoNode=pNode;
	  this.nextNode=nnode;
	}
}
public class Main {
	static node nodes[]=new node[10002];
	public static void init(int number)
	{
	     nodes[1]=new node(1, null, null);
	     nodes[1].forenoNode=nodes[1].nextNode=nodes[1];
	     for(int i=2;i<=number;i++)
	     {
	    	 nodes[i]=new node(i, null, null);
	    	 nodes[i].forenoNode=nodes[i-1];
	    	 nodes[i-1].nextNode=nodes[i];
	     }
	     nodes[1].forenoNode=nodes[number];
	     nodes[number].nextNode=nodes[1];
	}
	public static void changeA(int x,int y)
	{
		nodes[x].nextNode.forenoNode=nodes[x].forenoNode;
		nodes[x].forenoNode.nextNode=nodes[x].nextNode;
		nodes[x].forenoNode=nodes[y].forenoNode;
		nodes[x].nextNode=nodes[y];
		nodes[y].forenoNode.nextNode=nodes[x];
		nodes[y].forenoNode=nodes[x];
	}
	public static void changeB(int x,int y)
	{
		nodes[x].nextNode.forenoNode=nodes[x].forenoNode;
		nodes[x].forenoNode.nextNode=nodes[x].nextNode;
		nodes[x].forenoNode=nodes[y];
		nodes[x].nextNode=nodes[y].nextNode;
		nodes[y].nextNode.forenoNode=nodes[x];
		nodes[y].nextNode=nodes[x];
		
		
	}
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int cases = scanner.nextInt();
		while (cases-- != 0) {
            int number=scanner.nextInt();
            int times=scanner.nextInt();
            init(number);
            while(times--!=0)
            {
            	String string=scanner.next();
            	int x=scanner.nextInt();
            	int y=scanner.nextInt();
            	if(string.compareTo("A")==0)
            	{
            		if(x==y)continue;
            		changeA(x,y);//左面
            	}
            	else if(string.compareTo("B")==0){
            		if(x==y)continue;
					changeB(x, y); 
				}
            	else if(string.compareTo("Q")==0){
					if(x==1)
						System.out.println(nodes[y].nextNode.num);
					else {
						System.out.println(nodes[y].forenoNode.num);
					}
				}
            }
            
            
		}
	}

}