[数据结构与算法]蓝桥杯省赛夺奖冲刺营链表篇

蓝桥杯省赛夺奖冲刺营链表篇

「小王子单链表」

题目描述
小王子有一天迷上了排队的游戏，桌子上有标号为 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 = 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;
    }

    static   void 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 = 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 个人的出列顺序。

要求一：采用循环链表解决。

要求二：可以使用模拟法，模拟循环链表。

要求三：可以不使用循环链表类的定义使用方式。

输入描述
输入只有一行且为用空格隔开的三个正整数 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=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;
	}
}