13届蓝桥杯夺奖冲刺营|蓝桥杯省赛夺奖冲刺营链表篇蓝桥杯|数据结构|链表

蓝桥杯省赛夺奖冲刺营链表篇「小王子单链表」题目描述
小王子有一天迷上了排队的游戏，桌子上有标号为 1-101?10 的 1010 个玩具，现在小王子将他们排成一列，可小王子还是太小了，他不确定他到底想把那个玩具摆在哪里，直到最后才能排成一条直线，求玩具的编号。已知他排了 MM 次，每次都是选取标号为 XX 个放到最前面，求每次排完后玩具的编号序列。
要求一：采用单链表解决
输入描述
第一行是一个整数 MM，表示小王子排玩具的次数。
随后 MM 行每行包含一个整数 XX，表示小王子要把编号为 XX 的玩具放在最前面。
输出描述
共 MM 行，第 ii 行输出小王子第 ii 次排完序后玩具的编号序列。
输入输出样例
示例 1
输入

5 3 2 3 4 2

输出

3 1 2 4 5 6 7 8 9 10 2 3 1 4 5 6 7 8 9 10 3 2 1 4 5 6 7 8 9 10 4 3 2 1 5 6 7 8 9 10 2 4 3 1 5 6 7 8 9 10

运行限制
最大运行时间：1s
最大运行内存: 128M
代码

import java.util.Scanner; public class Main { static class Node { int data; Node next; Node(int v) { data = https://www.it610.com/article/v; } }//成员类，代表节点，类似于C++语言中的结构体static Node head = new Node(1); //头节点单列出来static void init() { Node x = head; for (int i = 1; i <= 10; i++) x = (x.next = new Node(i)); //建立单向链表 x.next = null; }staticvoid del(int x) {Node Befor = head; //用于存放当前节点的前驱，因为单链表单向遍历，我们不能从下一个找到上一个 for (Node T = head.next; T != null; T = T.next) //链表的遍历常用写法 { if (T.data == x) //找到要的那个数了 { Node temp = T; //先临时保存结点Befor.next = T.next; //将节点从链表上摘除return; //删除结束后，结束函数。 } Befor = T; //前驱改变 } }static void insert(int x) { Node temp = new Node(x); temp.next = head.next; head.next = temp; }static void show(int i) {//System.out.println("这是第" + i + "次操作"); //提交代码时删掉这一行for (Node T = head.next; T != null; T = T.next) //链表的遍历常用写法 { System.out.print(T.data + " "); } System.out.println(" "); }public static void main(String[] args) {int N; Scanner in = new Scanner(System.in); init(); N = in.nextInt(); // show(0); //提交代码时删掉这一行for (int i = 0; i < N; i++) { int x = in.nextInt(); del(x); insert(x); show(i); } } }

「小王子双链表」代码

iimport java.util.Scanner; public class Main { static class Node { int data; Node next; Node before; Node(int v) { data = https://www.it610.com/article/v; } } //成员类，代表节点，类似于C++语言中的结构体static Node head = new Node(1); //头节点单列出来static void init() { Node x = head; for (int i = 1; i<= 10; i++) { x.next = new Node(i); //建立双向链表 x.next.before = x; x = x.next; } x.next = null; }static void del(int x) {for (Node T = head.next; T != null; T = T.next) //链表的遍历常用写法 { if (T.data == x) //找到要的那个数了 { T.before.next = T.next; //将节点从链表上摘除T.next.before=T.before; return; //删除结束后，结束函数。 } } }static void insert(int x) { Node temp = new Node(x); temp.next = head.next; temp.next.before = temp; head.next = temp; }static void show(int i) {//System.out.println("这是第" + i + "次操作"); for (Node T = head.next; T != null; T = T.next) //链表的遍历常用写法 { System.out.print(T.data + " "); } System.out.println(" "); }public static void main(String[] args) {int N; //n个人从k位置开始报数，数到m出列Scanner in = new Scanner(System.in); init(); N = in.nextInt(); // show(0); for (int i = 0; i < N; i++) { int x = in.nextInt(); del(x); insert(x); show(i); } } }

「约瑟夫环」题目描述
设有 n 个人围坐在圆桌周围，现从某个位置 kk 上的人开始报数，报数到 m 的人就站出来。下一个人，即原来的第 m+1 个位置上的人，又从 1 开始报数，再报数到 m 的人站出来。依次重复下去，直到全部的人都站出来为止。试设计一个程序求出这 n 个人的出列顺序。
要求一：采用循环链表解决。
要求二：可以使用模拟法，模拟循环链表。
【13届蓝桥杯夺奖冲刺营|蓝桥杯省赛夺奖冲刺营链表篇】要求三：可以不使用循环链表类的定义使用方式。
输入描述
输入只有一行且为用空格隔开的三个正整数 n,k,m其含义如上所述。
输出描述
共 n 行，表示这 n 个人的出列顺序。
输入输出样例
示例 1
输入

3 5 8

输出

3 2 1

运行限制
最大运行时间：1s
最大运行内存: 128M
代码

import java.util.Scanner; public class Main { static class Node{//成员类 int data; Node right; Node(int v){ data=https://www.it610.com/article/v; } } static Node head=new Node(1); //头结点 public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n=sc.nextInt(); //人数 int k=sc.nextInt(); //开始 int m=sc.nextInt(); //报数 Node x=head; //建立单链表,x就像一个指针，x变head不会变 for (int i = 2; i <= n; i++) { x.right=new Node(i); x=x.right; } x.right=head; int start=k%n; Node befor=head; //要记录他的前一个人 int t=m%n; for (Node i = head; ; i=i.right) { if(i.data==start) {//起始位置开始循环 find(befor,i, t); //找到那个人并删除 break; } befor=i; } } private static void find(Node befor,Node i, int t) { while(i.right!=i) { int temp=t; for (; temp> 1; temp--) { befor=i; i=i.right; } System.out.println(i.data); //打印 befor.right=i.right; //删除 i=i.right; } System.out.println(i.data); return; } }