本文共 44506 字，大约阅读时间需要 148 分钟。

目录

bilibili尚硅谷韩顺平老师课程的笔记。

 

数据结构和算法简介

数据结构与算法的重要性：

• 算法是程序的灵魂，优秀的程序可以在海量数据计算时，依然保持高速计算；
• 一般来讲，程序会使用了内存计算框架(比如Spark)和缓存技术(比如Redis等)来优化程序,再深入的思考一下，这些计算框架和缓存技术， 它的核心功能是哪个部分呢？
• 拿实际工作经历来说, 在Unix下开发服务器程序，功能是要支持上千万人同时在线， 在上线前，做内测，一切OK,可上线后，服务器就支撑不住了, 公司的CTO对代码进行优化，再次上线，坚如磐石。你就能感受到程序是有灵魂的，就是算法；
• 目前程序员面试的门槛越来越高，很多一线IT公司(大厂)，都会有数据结构和算法面试题(负责的告诉你，肯定有的)；
• 如果你不想永远都是代码工人,那就花时间来研究下数据结构和算法。

数据结构和算法的关系：

• 数据data结构(structure)是一门研究组织数据方式的学科，有了编程语言也就有了数据结构.学好数据结构可以编写出更加漂亮,更加有效率的代码；
• 要学习好数据结构就要多多考虑如何将生活中遇到的问题,用程序去实现解决；
• 程序 = 数据结构 + 算法；
• 数据结构是算法的基础, 换言之，想要学好算法，需要把数据结构学到位。

数据结构包括：（线性结构、非线性结构）

线性结构：

• 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系；
• 线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构；
• 顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的；
• 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息；
• 线性结构常见的有：数组、队列、链表和栈；

非线性结构：非线性结构包括：二维数组，多维数组，广义表，树结构，图结构。

 

稀疏数组

应用：使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等) 把稀疏数组存盘，并且可以从新恢复原来的二维数组数。

代码 ：

package com.jiao.dataStructure;import java.io.*;import java.util.ArrayList;import java.util.List;public class SparseArr {    public static void main(String[] args) {        //创建二维数组rootArr[11][11]：0-无棋子，1-黑子，2-白子        int rootArr[][] = new int[11][11];        rootArr[1][2] = 1;        rootArr[2][3] = 2;        //遍历rootArr        System.out.println("===================原始数组================");        for (int[] row1 : rootArr) {            for (int data : row1) {                System.out.printf("%d\t",data);            }            System.out.println();        }        /**          二维数组 转 稀疏数组 的思路             1. 遍历 原始的二维数组，得到有效数据的个数sum；             2. 根据sum的值就可以创建 稀疏数组sparseArr int[sum+1][3]；             3. 将二维数组的有效数据存入到 稀疏数组。         */        int sum=0;  //原始数组有效数据个数统计        for (int[] row2 : rootArr) {            for (int data : row2) {                if (data != 0){                    sum ++;                }            }        }        System.out.println("原始数组有效数据个数："+sum);        int sparseArr[][] = new int[sum+1][3];  //创建稀疏数组        //稀疏数组第一行固定：[0][0]、[0][1]原数组行列数，[0][2]原数组有效数值个数        sparseArr[0][0]=11;        sparseArr[0][1]=11;        sparseArr[0][2]=sum;        //遍历原数组，将有效数值赋值给稀疏数组        int row = 1;    //稀疏数组从第二行开始，每一行进行sum次写入        for (int i = 0; i < 11; i++) {            for (int j = 0; j < 11; j++) {                if (rootArr[i][j] != 0){    //原始数组=1,写入稀疏数组                    sparseArr[row][0] = i;                    sparseArr[row][1] = j;                    sparseArr[row][2] = rootArr[i][j];                    row ++;                }            }        }        //输出稀疏数组        System.out.println("==============原始数组 转 稀疏数组===========");        for (int[] row3 : sparseArr) {            for (int data : row3) {                System.out.printf("%d\t",data);            }            System.out.println();        }        //作业1：将稀疏数组写进文件        //作业2：将文件的稀疏数组读出来/*        System.out.println("=================读取文件的稀疏数组=================");        for (int[] row6 : sparseArr1) {            for (int data : row6) {                System.out.printf("%d\t",data);            }            System.out.println();        }*/        /**          稀疏数组 转 原始的二维数组 的思路             1. 先读取稀疏数组的第一行，根据第一行的数据‘’‘’‘’‘’，创建原始的二维数组，比如图片中的 chessArr2=int[11][11]；             2. 再读取稀疏数组后几行的数据，并赋给 原始二维数组 即可。         */        System.out.println("==============稀疏数组 转 原始数组===========");        int rowChange = sparseArr1[0][0];        int colChange = sparseArr1[0][1];        System.out.println("原数组row："+rowChange+"\t原数组col："+colChange);        int changeArr[][] = new int[rowChange][colChange];  //根据读取的稀疏数组第一行创建要恢复的二维数组        for (int i = 1; i <= sparseArr[0][2]; i++) {            changeArr[sparseArr1[i][0]][sparseArr1[i][1]] = sparseArr1[i][2];      //把稀疏数组每行row、col、val 读出来做出相应的赋值        }        //输出恢复的二维数组        for (int[] row4 : changeArr) {            for (int data : row4) {                System.out.printf("%d\t",data);            }            System.out.println();        }    }}

作业：

• 在前面的基础上，将稀疏数组保存到磁盘上，比如 map.data；
• 恢复原来的数组时，读取map.data 进行恢复。

//作业1：将稀疏数组写进文件        //1.创建字符输出流        FileWriter writer = null;        try {            //2.数据写入的路径            File file = new File("map.data");            //3.文件不存在就创建            if (!file.exists()){                file.createNewFile();            }            //4.给字符输出流赋予实例            writer = new FileWriter(file);            //5.稀疏数组循环写入文档            for (int i = 0; i < sparseArr.length; i++) {                //6.以|分隔每行前n-1个数据                for (int j = 0; j < sparseArr[0].length-1; j++) {                    writer.write(sparseArr[i][j]+"|");                }                //7.数组最后一行不加|                writer.write(sparseArr[i][sparseArr[0].length-1]+"");                //8.加上换行符                writer.write("\n");            }            //9.把writer数据刷新一次，全部写入文件中            writer.flush();        } catch (IOException e) {            e.printStackTrace();        } finally {            //10.假如writer不为空，就将其关闭            if (writer != null){                try {                    writer.close();                    System.out.println("稀疏数组写入完成...");                } catch (IOException e) {                    e.printStackTrace();                    System.out.println("稀疏数组写入失败...");                }            }        }//作业2：将文件的稀疏数组读出来        //1.申明一个字符输入流        FileReader reader = null;        //2.申明一个字符输入缓冲流        BufferedReader readerBuf = null;        //3.申明一个从文件中读取的二维数组（稀疏数组changeArr1）        int sparseArr1[][] = null;        try {            //4.指定reader的读取路径            reader = new FileReader("map.data");            //5.通过BufferReader包装字符流            readerBuf = new BufferedReader(reader);            //6.创建一个List集合，用来存放读取的文件数据            List
   
     strList = new ArrayList<>();            //7.用来存放一行的数据            String lineStr;            //8.逐行读取文件的内容            while ((lineStr = readerBuf.readLine()) != null){                //9.把读取的行添加到List中                strList.add(lineStr);            }            //10.获取文件的行数            int lineNum = strList.size();            //11.获取数组的列数            String s = strList.get(0);            int columnNum = s.split("\\|").length;            //12.根据行列创建数组            sparseArr1 = new int[lineNum][columnNum];            //13.记录输出当前行            int count = 0;            //14.循环遍历集合，把集合中的数据放入数组中            for (String str : strList) {                //15.将读取的str按照“|”分割，用字符串数组接收                String[] strs = str.split("\\|");                for (int i = 0; i < columnNum; i++) {                    sparseArr1[count][i] = Integer.valueOf(strs[i]);                }                //16.将行数+1                count ++;            }        } catch (Exception e) {            e.printStackTrace();        } finally {            //17.关闭字符输入流            try {                reader.close();            } catch (IOException e) {                e.printStackTrace();            }            //18.关闭字符输入缓冲流            try {                readerBuf.close();            } catch (IOException e) {                e.printStackTrace();            }        }
   

 复习：数组、列表、文件操作

 

队列

队列介绍：

• 队列是一个有序列表，可以用数组或是链表来实现；
• 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出；
• 示意图：(使用数组模拟队列示意图)：

数组模拟队列：

• 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如上图, 其中 maxSize 是该队列的最大容量；
• 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变。
• 当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思路分析
• 将尾指针往后移：rear+1 , 当front == rear 【空】
• 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。 rear  == maxSize - 1[队列满]

1. 写一个类：Class arrayQueue{    - //变量、构造器    - //创建队列的构造器    - //判断队列是否为空 boolean isEmpty();    - //判断队列是否满 boolean isFull();    - //添加数据到队列（判断满？rear++） void addQueue(int n);    - //获取队列的数据，出队列（判断空？抛异常，front++） int getQueue();    - //显示队列的所有数据（遍历，判断空？） void showQueue();    - //显示队列的头数据（不是取数据，判断空？） int headQueue();}2. 测试： switch语句：   - show:显示队列、   - exit：退出队列、   - add：添加数据到队列、   - get：从队列中取数据、   - head：查看队列头的数据3.问题：一次性数组。

代码：

package com.jiao.dataStructure;import java.util.Scanner;public class ArrayQueue {    public static void main(String[] args) {        //创建一个队列        arrQueue queue = new arrQueue(3);        //接收用户的输入菜单        char key = ' ';        Scanner scanner = new Scanner(System.in);        boolean loop = true;    //菜单循环        while (loop){            //输出一个菜单            System.out.println("----------------");            System.out.println("s(show):显示队列");            System.out.println("e(exit):退出队列");            System.out.println("a(add):添加数据到队列");            System.out.println("g(get):从队列中取数据");            System.out.println("h(head):查看队列头的数据");            key = scanner.next().charAt(0);            switch (key){                case 's':                    queue.showQueue();                    break;                case 'a':                    System.out.printf("添加一条数：");                    int data = scanner.nextInt();                    queue.addQueue(data);                    break;                case 'g':                    try {                        int result = queue.getQueue();                        System.out.printf("队列获取的数据是：%d",result);                    } catch (Exception e){                        System.out.println(e.getMessage());                    }                    break;                case 'h':                    try {                        int headQueue = queue.headQueue();                        System.out.printf("队列获取的头数据是：%d",headQueue);                    } catch (Exception e){                        System.out.println(e.getMessage());                    }                    break;                case 'e':                    scanner.close();                    loop=false;                    break;                default:                    break;            }        }        System.out.println("程序已经退出。");    }}//数组模拟队列类class arrQueue{    //数组模拟队列所需的变量    private int maxSize; //数组队列的容量    private int front; //数组队列的最前元素    private int rear; //数组队列的最后元素    private int[] arr; //数组队列数据    //构造器    public arrQueue(int size){        maxSize = size;        arr = new int[size]; //创建 包含容量的队列数据        front = -1; //指向队列的前一个位置，不包含此位置        rear = -1; //指向队列的最后一个位置，包含此位置    }    //判断队列是否满    public boolean isFull(){        return rear == maxSize - 1;    }    //判断队列是否为空    public boolean isEmpty(){        return front == rear;    }    //添加数据到队列    public void addQueue(int n){        if (isFull()){            System.out.println("队列满了,不能加数据。");            return;        }        rear++;        arr[rear]=n;    }    //获取队列的数据，出队列    public int getQueue(){        if (isEmpty())            throw new RuntimeException("队列为空，没有数据~");        front++;        return arr[front];    }    //显示队列所有的数据    public void showQueue(){        if (isEmpty()){            System.out.println("队列为空，没有数据~");            return;        }        for (int i = 0; i < arr.length; i++) {            System.out.printf("arr[%d]=%d, ",i,arr[i]);        }        System.out.println();    }    //显示队列的头数据    public int headQueue(){        if (isEmpty()){            System.out.println("队列为空，没有数据~");            return -1;        }        return front+1;    }}

结果测试：

问题：队列只能使用一次。

数组模拟环形队列：

思路：

• front指向队列的第一个元素：初始值front = 0；
• real指向队列最后一个元素的后一个位置(预留空间)：初始值real = 0；
• 队列满：(rear+1)%maxSize==front；
• 队列空：rear==front；
• 有效数据个数：(rear+maxSize-front)%maxSize。

代码：

package com.jiao.dataStructure;import java.util.Scanner;public class CircleArrayQueue {    public static void main(String[] args) {        //创建一个队列        circleQueue queue = new circleQueue(4);        //接收用户的输入菜单        char key = ' ';        Scanner scanner = new Scanner(System.in);        boolean loop = true;    //菜单循环        while (loop){            //输出一个菜单            System.out.println("----------------");            System.out.println("s(show):显示队列");            System.out.println("e(exit):退出队列");            System.out.println("a(add):添加数据到队列");            System.out.println("g(get):从队列中取数据");            System.out.println("h(head):查看队列头的数据");            key = scanner.next().charAt(0);            switch (key){                case 's':                    queue.showQueue();                    break;                case 'a':                    System.out.printf("添加一条数：");                    int data = scanner.nextInt();                    queue.addQueue(data);                    break;                case 'g':                    try {                        int result = queue.getQueue();                        System.out.printf("队列获取的数据是：%d",result);                    } catch (Exception e){                        System.out.println(e.getMessage());                    }                    break;                case 'h':                    try {                        int headQueue = queue.headQueue();                        System.out.printf("队列获取的头数据是：%d",headQueue);                    } catch (Exception e){                        System.out.println(e.getMessage());                    }                    break;                case 'e':                    scanner.close();                    loop=false;                    break;                default:                    break;            }        }        System.out.println("程序已经退出。");    }}//数组模拟环形队列class circleQueue {    //数组模拟队列所需的变量    private int maxSize; //数组队列的容量    private int front; //数组队列的最前元素    private int rear; //数组队列的最后元素    private int[] arr; //数组队列数据    //构造器    public circleQueue(int size) {        maxSize = size;        arr = new int[size]; //创建 包含容量的队列数据        front = 0; //指向队列的第一个位置        rear = 0; //指向队列的最后一个位置    }    //判断队列是否满    public boolean isFull() {        return (rear + 1) % maxSize == front;    }    //判断队列是否为空    public boolean isEmpty() {        return front == rear;    }    //添加数据到队列    public void addQueue(int n) {        if (isFull()) {            System.out.println("队列满了,不能加数据。");            return;        }        arr[rear] = n;    //real初始为0,先使用再指向预留字段        rear = (rear + 1) % maxSize;    //不能单纯的rear++    }    //获取队列的数据，出队列    public int getQueue() {        if (isEmpty())            throw new RuntimeException("队列为空，没有数据~");        //front指向第一个元素        //1.front保存临时变量(不保存后移就找不到了)        //2.front后移        //3.返回临时变量        int value = arr[front];        front = (front+1)%maxSize;        return value;    }    //显示队列所有的数据    public void showQueue(){        if (isEmpty()){            System.out.println("队列为空，没有数据~");            return;        }        //从front开始遍历，遍历多少个数据        for (int i = front; i < front+size(); i++) {            System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);        }        System.out.println();    }    //有效数据个数(n-1),第n个是预留空间    //获取当前循环队列数据个数    public int size(){        return (rear+maxSize-front)%maxSize;    }    //显示队列的头数据    public int headQueue(){        if (isEmpty()){            System.out.println("队列为空，没有数据~");            return -1;        }        return front;    }}

测试结果：

复习：类、对象、构造器等

 

链表

单向链表： 

案例：

• 使用带head头的单向链表实现 –水浒英雄排行榜管理 完成对英雄人物的增删改查操作，
• 第一种方法在添加英雄时，直接添加到链表的尾部；
• 第二种方式在添加英雄时，根据排名将英雄插入到指定位置 (如果有这个排名，则添加失败，并给出提示) 。

1. 创建(添加)和遍历

class HeroNode{    int no;     String name;     String nickname;     HeroNode next;}

添加：  

• 先创建一个head头结点，作用就是表示单链表的头  
• 后面每添加一个节点，就直接加入到 链表的最后  

遍历：  

• 通过一个辅助变量遍历，帮助遍历整个链表 

代码：

package com.jiao.dataStructure;public class SingleLinkedList {    public static void main(String[] args) {        //test        //先创建节点数据        HeroNode heroNode1 = new HeroNode(1,"松江","及时雨");        HeroNode heroNode2 = new HeroNode(2,"鲁智深","花和尚");        HeroNode heroNode3 = new HeroNode(3,"李逵","黑旋风");        HeroNode heroNode4 = new HeroNode(4,"林冲","豹子头");        //创建链表        HeroManagement heroes = new HeroManagement();        //加入        heroes.add(heroNode1);        heroes.add(heroNode2);        heroes.add(heroNode3);        heroes.add(heroNode4);        //显示        heroes.list();    }}//定义HeroManagement，管理我们的英雄class HeroManagement {    //初始化头节点，头结点不要动，不存放数据    private HeroNode head = new HeroNode(0,"","");    //1.添加节点到单向链表    //思路(不考虑编号顺序)：   1.找到当前链表的最后节点； 2.将最后这个节点next，指向 新的节点    public void add(HeroNode heroNode) {        //head节点不能动，用辅助遍历temp        HeroNode temp = head;  //临时存放头节点        while (true) {            if (temp.next == null) {    //找到链表的最后                break;            }            temp = temp.next;   //没找到temp后移        }        temp.next = heroNode;   //while退出循环，temp指向最后，找到了    }    //2.显示遍历    public void list() {        //判断链表是否为空        if (head.next == null) {            System.out.println("链表为空~~~");            return;        }        //辅助temp来遍历        HeroNode temp = head.next;        while (true) {            if (temp == null) { //判断链表到最后                break;            }            System.out.println(temp);   //打印            temp = temp.next;   //指向下一个节点        }    }}//定义HeroNode，每一个HeroNode 对象就是一个节点class HeroNode {    //变量    public int no; //英雄编号    public String name; //英雄名字    public String nickname; //英雄昵称    public HeroNode next;  //下一个节点地址    //构造器    public HeroNode(int no, String name, String nickname) {        this.no = no;        this.name = name;        this.nickname = nickname;    }    //为了显示方便，重新toString    @Override    public String toString() {        return "HeroNode{" +                "no=" + no +                ", name='" + name + '\'' +                ", nickname='" + nickname + '\'' +                '}';    }}

测试：

2. 添加(按照编号顺序)

• a. 首先找到新添加的节点的位置，是通过辅助变量(指针),遍历;
• b. 新的节点.next=temp.next;
• c. 将temp.next=新的节点。

代码：

package com.jiao.dataStructure;public class SingleLinkedList {    public static void main(String[] args) {        //test        //先创建节点数据        HeroNode heroNode1 = new HeroNode(1,"松江","及时雨");        HeroNode heroNode2 = new HeroNode(2,"鲁智深","花和尚");        HeroNode heroNode3 = new HeroNode(3,"李逵","黑旋风");        HeroNode heroNode4 = new HeroNode(4,"林冲","豹子头");        //创建链表        HeroManagement heroes = new HeroManagement();        //加入        heroes.addByOrder(heroNode1);        heroes.addByOrder(heroNode4);        heroes.addByOrder(heroNode3);        heroes.addByOrder(heroNode2);        heroes.addByOrder(heroNode2);        //显示        heroes.list();    }}//定义HeroManagement，管理我们的英雄class HeroManagement {    //初始化头节点，头结点不要动，不存放数据    private HeroNode head = new HeroNode(0,"","");...    //添加的第二种方法    public void addByOrder(HeroNode heroNode) {        //1. 找到No的前一个位置,temp变量,遍历        HeroNode temp = head;   //临时变量存放头指针        boolean flag = false;   //是否重复的标志        while (true) {            if (temp.next == null) {    //找到了最后                break;            }            if (temp.next.no > heroNode.no) {   //temp.next的no开始大于要插入的no,说明当前的temp找到了                break;            } else if ( temp.next.no == heroNode.no) {  //要添加的no在链表存在了                flag = true;                break;            }            temp = temp.next;        }                //2.通过flag,判定添加        if (flag) {            System.out.printf("准备插入的英雄编号:%d已经存在,不能添加！\n",heroNode.no);        } else {            heroNode.next = temp.next;  //temp.next的指向 放在 HeroNode.next的指向            temp.next = heroNode;   //把要插入的节点 放在 temp.next        }    }...   }

测试结果：

3.节点的修改（根据编号修改，不修改编号）

代码段：

package com.jiao.dataStructure;public class SingleLinkedList {    public static void main(String[] args) {        //test        //先创建节点数据        HeroNode heroNode1 = new HeroNode(1,"松江","及时雨");        HeroNode heroNode2 = new HeroNode(2,"鲁智深","花和尚");        HeroNode heroNode3 = new HeroNode(3,"李逵","黑旋风");        HeroNode heroNode4 = new HeroNode(4,"林冲","豹子头");        //创建链表        HeroManagement heroes = new HeroManagement();        //加入(按照编号排序)        heroes.addByOrder(heroNode1);        heroes.addByOrder(heroNode4);        heroes.addByOrder(heroNode3);        heroes.addByOrder(heroNode2);        //修改        System.out.println("修改前：");        heroes.list();  //修改前        HeroNode newHero = new HeroNode(2,"鲁智深1","花和尚1");        heroes.update(newHero);        //显示        System.out.println("修改后：");        heroes.list();  //修改后    }}//定义HeroManagement，管理我们的英雄class HeroManagement {    //初始化头节点，头结点不要动，不存放数据    private HeroNode head = new HeroNode(0,"","");...    //3.修改(根据新的数据的no修改)    public void update(HeroNode newHeroNode) {        if (head.next == null) {    //判断是否为空            System.out.println("链表为空~");            return;        }        HeroNode temp = head.next;   //辅助变量        boolean flag = false;   //标志是否找到        while (true) {            if (temp.next  == null) {       //到了链表最后，没有找到同 no                break;            }            if (temp.no == newHeroNode.no) {  //找到no相同的temp                flag = true;                break;            }            temp = temp.next;        }        if (flag) { //找到了            temp.name = newHeroNode.name;            temp.nickname = newHeroNode.nickname;        } else {    //没找到            System.out.printf("没有找到要修改的no=%d的节点。",newHeroNode.no);        }    }}...

测试结果：

4.删除节点

• a. 先找到 需要删除的 这个节点的前一个节点temp
• b. temp.next = temp.next.next
• c. 被删除的节点，将不会有其他引用指向，会被垃圾回收

代码段：

package com.jiao.dataStructure;public class SingleLinkedList {    public static void main(String[] args) {        //test        //先创建节点数据        HeroNode heroNode1 = new HeroNode(1,"松江","及时雨");        HeroNode heroNode2 = new HeroNode(2,"鲁智深","花和尚");        HeroNode heroNode3 = new HeroNode(3,"李逵","黑旋风");        HeroNode heroNode4 = new HeroNode(4,"林冲","豹子头");        //创建链表        HeroManagement heroes = new HeroManagement();        //加入(按照编号排序)        heroes.addByOrder(heroNode1);        heroes.addByOrder(heroNode4);        heroes.addByOrder(heroNode3);        heroes.addByOrder(heroNode2);        //heroes.addByOrder(heroNode2);        //删除        heroes.del(2);        heroes.del(2);        //heroes.del(4);        //heroes.del(3);        //显示        //System.out.println("修改后：");        heroes.list();      }}//定义HeroManagement，管理我们的英雄class HeroManagement {    //初始化头节点，头结点不要动，不存放数据    private HeroNode head = new HeroNode(0,"","");...    //4.删除(根据no)    public void del(int no){        //找到需要删除的节点的前一个：temp.next.no = no        if (head.next == null) {    //判断是否为空            System.out.println("链表为空~");            return;        }        HeroNode temp = head;   //辅助变量        boolean flag = false;   //标志是否找到        while (true){            if (temp.next ==null){  //到链表最后也没找到                break;            }            if (temp.next.no == no){    //找到了，temp是找到的前一个节点                flag = true;                break;            }            temp = temp.next;        }        if (flag){            temp.next = temp.next.next;     //前一个的next地址 = 要删除的节点的next(指向的是要删除节点的下一个节点)        } else {            System.out.printf("没有找到要删除的节点no=%d。\n",no);        }    }}...

测试结果：

面试题：

• 1. 求单链表中有效节点的个数(不统计头结点)

代码段：

package com.jiao.dataStructure;public class SingleLinkedList {    public static void main(String[] args) {        //test        //先创建节点数据        HeroNode heroNode1 = new HeroNode(1,"松江","及时雨");        HeroNode heroNode2 = new HeroNode(2,"鲁智深","花和尚");        HeroNode heroNode3 = new HeroNode(3,"李逵","黑旋风");        HeroNode heroNode4 = new HeroNode(4,"林冲","豹子头");        //创建链表        HeroManagement heroes = new HeroManagement();        //加入(按照编号排序)        heroes.addByOrder(heroNode1);        heroes.addByOrder(heroNode4);        heroes.addByOrder(heroNode3);        heroes.addByOrder(heroNode2);        //heroes.addByOrder(heroNode2);        //删除        heroes.del(2);        //显示        heroes.list();  //修改后        //测试：获取单链表个数        System.out.println("有效节点个数："+getLength(heroes.getHead()));    }    //1. 求单链表中有效节点的个数(不统计头结点)    public static int getLength(HeroNode head){        if (head.next == null)  {   //空链表            return 0;        }        HeroNode cur = head.next;    //临时变量        int length = 0;     //统计个数        while (cur != null) {   //遍历            length++;            cur = cur.next; //指针后移        }        return length;    }}//定义HeroManagement，管理我们的英雄class HeroManagement {    //初始化头节点，头结点不要动，不存放数据    private HeroNode head = new HeroNode(0,"","");    public HeroNode getHead() {        return head;    }    ...}//定义HeroNode，每一个HeroNode 对象就是一个节点class HeroNode {...}

测试结果：

• 2. 查找单链表中的倒数第k个结点 【新浪面试题】

步骤：

1. 编写一个方法，接收head节点，同时接收一个index(表示倒数第index个节点)
2. 把链表从头到尾遍历，得到链表的总长度 (调用getLength()方法)
3. 得到size后，从链表的第一个开始遍历(size-index)个，就可以得到

代码段：

package com.jiao.dataStructure;public class SingleLinkedList {    public static void main(String[] args) {        //test        //先创建节点数据        HeroNode heroNode1 = new HeroNode(1,"松江","及时雨");        HeroNode heroNode2 = new HeroNode(2,"鲁智深","花和尚");        HeroNode heroNode3 = new HeroNode(3,"李逵","黑旋风");        HeroNode heroNode4 = new HeroNode(4,"林冲","豹子头");        //创建链表        HeroManagement heroes = new HeroManagement();        //加入(按照编号排序)        heroes.addByOrder(heroNode1);        heroes.addByOrder(heroNode4);        heroes.addByOrder(heroNode3);        heroes.addByOrder(heroNode2);        //heroes.addByOrder(heroNode2);        //删除        heroes.del(2);        //显示        //System.out.println("修改后：");        heroes.list();  //修改后        //测试：输出倒数第k个节点        int index = 1;        HeroNode heroNo = listOneHeroNode(heroes.getHead(), index);        System.out.println("倒数第"+index+"节点是："+heroNo);    }    //2. 查找单链表中的倒数第k个结点 【新浪面试题】    /*    分析：        1) 编写一个方法，接收head节点，同时接收一个index(表示倒数第index个节点)        2) 把链表从头到尾遍历，得到链表的总长度 (调用getLength()方法)        3) 得到size后，从链表的第一个开始遍历(size-index)个，就可以得到    */    public static HeroNode listOneHeroNode(HeroNode head, int index){        if (head.next == null) {            System.out.println("链表为空~");            return null;        }        int size = getLength(head);     //链表有效个数        HeroNode temp = head.next;  //temp指向head后一个        int sum = 0;//统计正查询个数        if (size < index || index <=0 ){            System.out.println("查询的倒数第"+index+"节点不存在~");            return null;    //返回null        } else {            while (temp != null) {  //遍历                if (sum == (size - index)) {                    break;                }                temp = temp.next;   //后移                sum++;            }        }        //老师的方法        /*for (int i = 0; i < size - index; i++) {            temp = temp.next;        }*/        return temp;    }    ...}//定义HeroManagement，管理我们的英雄class HeroManagement {    //初始化头节点，头结点不要动，不存放数据    private HeroNode head = new HeroNode(0,"","");    public HeroNode getHead() {        return head;    }    ...}//定义HeroNode，每一个HeroNode 对象就是一个节点class HeroNode {...}

 测试结果：

• 3. 单链表的反转【腾讯面试题，有点难度】

步骤：

• a) 先定义一个节点reverseHead = new HeroNode();
• b) 从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前面;
• c) 原来的链表的head.next = reverseHead.next;

代码：

package com.jiao.dataStructure;public class SingleLinkedList {    public static void main(String[] args) {        //test        //先创建节点数据        HeroNode heroNode1 = new HeroNode(1,"松江","及时雨");        HeroNode heroNode2 = new HeroNode(2,"鲁智深","花和尚");        HeroNode heroNode3 = new HeroNode(3,"李逵","黑旋风");        HeroNode heroNode4 = new HeroNode(4,"林冲","豹子头");        //创建链表        HeroManagement heroes = new HeroManagement();        //加入(按照编号排序)        heroes.addByOrder(heroNode1);        heroes.addByOrder(heroNode4);        heroes.addByOrder(heroNode3);        heroes.addByOrder(heroNode2);        //显示        System.out.println("修改前：");        heroes.list();        reverseList(heroes.getHead());        System.out.println("修改后：");        heroes.list();    }    /*    3. 单链表的反转【腾讯面试题，有点难度】        步骤：            a) 先定义一个节点reverseHead = new HeroNode();            b) 从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前面;            c) 原来的链表的head.next = reverseHead.next;    */    public static void reverseList(HeroNode head){        //如果当前的链表为空，或者只有一个节点，无需反转，直接返回        if (head.next == null || head.next.next == null) {            return;        }        //定义一个辅助的指针(变量)cur，帮助我们遍历原来的链表，next：cur的下一个节点        HeroNode cur = head.next;        HeroNode next = null;        //a.新链表reverseHead        HeroNode reverseHead = new HeroNode(0,"","");        //b.遍历        while (cur != null) {            next = cur.next;    //临时保存要取走的节点的下一个节点            cur.next = reverseHead.next;    //取后 先连接reverseHead的原来的头结点的下一个，再把新的放在最前面            reverseHead.next = cur;     //取出的节点放在reverseHead的最前面            cur = next; //当前节点的下一个        }        //c.把reverseHead头换成head的头节点        head.next = reverseHead.next;    }}//定义HeroManagement，管理我们的英雄class HeroManagement {    //初始化头节点，头结点不要动，不存放数据    private HeroNode head = new HeroNode(0,"","");    public HeroNode getHead() {        return head;    }...}//定义HeroNode，每一个HeroNode 对象就是一个节点class HeroNode {...}

测试结果：

• 4. 从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】

代码：

package com.jiao.dataStructure;import java.util.Stack;public class SingleLinkedList {    public static void main(String[] args) {        //test        //先创建节点数据        HeroNode heroNode1 = new HeroNode(1,"松江","及时雨");        HeroNode heroNode2 = new HeroNode(2,"鲁智深","花和尚");        HeroNode heroNode3 = new HeroNode(3,"李逵","黑旋风");        HeroNode heroNode4 = new HeroNode(4,"林冲","豹子头");        //创建链表        HeroManagement heroes = new HeroManagement();        //加入(按照编号排序)        heroes.addByOrder(heroNode1);        heroes.addByOrder(heroNode4);        heroes.addByOrder(heroNode3);        heroes.addByOrder(heroNode2);        //显示        System.out.println("修改前：");        heroes.list();        System.out.println("用栈反转打印链表数据：");        reversePrint(heroes.getHead());        System.out.println("修改后：");        heroes.list();    }    //4.利用栈这个数据结构，将各个节点压到栈中，利用栈的先进后出特点，实现逆序打印    public static void reversePrint(HeroNode head){        //判断空        if (head.next == null) {            return;        }        //创建栈stack，将各个节点压入栈中 push        Stack
   
     stack = new Stack<>();        HeroNode cur = head.next;   //临时变量        while (cur != null) {            stack.push(cur);    //链表节点入栈            cur = cur.next;        }        //将栈中的节点打印，pop出栈        while (stack.size() > 0) {            System.out.println(stack.pop());        }    }...}//定义HeroManagement，管理我们的英雄class HeroManagement {    //初始化头节点，头结点不要动，不存放数据    private HeroNode head = new HeroNode(0,"","");    public HeroNode getHead() {        return head;    }...}//定义HeroNode，每一个HeroNode 对象就是一个节点class HeroNode {...}
   

 测试结果：

• 5. 合并两个有序的单链表，合并之后的链表依然有序【课后练习作业】

代码：

package com.jiao.dataStructure;import java.util.Stack;public class SingleLinkedList {    public static void main(String[] args) {        //test        //先创建节点数据        HeroNode heroNode1 = new HeroNode(1,"松江","及时雨");        HeroNode heroNode2 = new HeroNode(2,"鲁智深","花和尚");        HeroNode heroNode3 = new HeroNode(3,"李逵","黑旋风");        HeroNode heroNode4 = new HeroNode(4,"林冲","豹子头");        HeroNode heroNode5 = new HeroNode(5,"公孙胜","入云龙");        HeroNode heroNode6 = new HeroNode(6,"花荣","小李广");        HeroNode heroNode7 = new HeroNode(7,"柴进","小旋风");        HeroNode heroNode8 = new HeroNode(8,"张顺 ","浪里白条");        //创建链表        HeroManagement heroes1 = new HeroManagement();        HeroManagement heroes2 = new HeroManagement();        //加入(按照编号排序)        heroes1.addByOrder(heroNode1);        heroes1.addByOrder(heroNode4);        heroes1.addByOrder(heroNode8);        heroes1.addByOrder(heroNode5);        //heroes2.addByOrder(heroNode3);        heroes2.addByOrder(heroNode7);        heroes2.addByOrder(heroNode6);        heroes2.addByOrder(heroNode2);        //显示        System.out.println("修改前：");        heroes1.list();        System.out.println("-----");        heroes2.list();        System.out.println("两个链表合并：");        HeroNode combination = listDoubleCombination(heroes1.getHead(), heroes2.getHead());        HeroNode temp = combination.next;        while (temp != null) {            System.out.println(temp.toString());            temp = temp.next;        }    }    /*    5. 合并两个有序的单链表，合并之后的链表依然有序【no排序】    思路： 依次比较两个有序的链表，再放入新的链表    */    public static HeroNode listDoubleCombination(HeroNode head1, HeroNode head2) {        //判断为空        if (head1.next == null && head2.next == null) {            return null;        }        if (head1.next == null && head2.next != null) {            return head2;   //head1无节点，head2有节点        }        if (head1.next != null && head2.next == null) {            return head1;   //head1有节点，head2无节点        }        //定义两个临时链表，方便遍历。  定义一个合并的链表        HeroNode cur1 = head1.next;        HeroNode cur2 = head2.next;        HeroNode combinationHead = new HeroNode(0,"","");        HeroNode comCur = combinationHead;        //对两个链表遍历比较no        while (cur1 != null && cur2 != null) {            if (cur1.no < cur2.no) {                comCur.next = cur1;                comCur = comCur.next;                cur1 = cur1.next;            } else if (cur1.no == cur2.no) {                comCur.next = cur1;                comCur = comCur.next;                //或者                /*combinationHead.next = cur2;                combinationHead = combinationHead.next;*/                cur1 = cur1.next;                cur2 = cur2.next;            } else {                comCur.next = cur2;                comCur = comCur.next;                cur2 = cur2.next;            }        }        //有一个链表比较完了，剩下一个链表直接放在新链表的后面        if (cur1 != null) {           comCur.next = cur1;           comCur = comCur.next;           cur1 = cur1.next;        }        if (cur2 != null) {            comCur.next = cur2;            comCur = comCur.next;            cur2 = cur2.next;        }        return combinationHead;    }...}//定义HeroManagement，管理我们的英雄class HeroManagement {    //初始化头节点，头结点不要动，不存放数据    private HeroNode head = new HeroNode(0,"","");    public HeroNode getHead() {        return head;    }...}//定义HeroNode，每一个HeroNode 对象就是一个节点class HeroNode {...}

测试结果：

双链表

1) 遍历： 方法和单链表一样，只是可以向前，也可以向后

2) 添加： (默认添加到双向链表的最后)

• (1) 先找到双向链表的最后这个节点
• (2) temp.next = newHeroNode
• (3) newHeroNode.pre = temp

3) 修改：思路和原理和单向链表一样

4) 删除

• (1) 因为是双向链表，因此，我们可以实现自我删除某个节点
• (2) 直接找到要删除的的这个节点，比如temp
• (3) temp.pre.next = temp.next
• (4) temp.next.pre = temp.pre

代码：

package com.jiao.dataStructure;public class DoubleLinkedList {    public static void main(String[] args) {        //先创建节点数据        HeroNode2 heroNode1 = new HeroNode2(1,"宋江","及时雨");        HeroNode2 heroNode2 = new HeroNode2(2,"鲁智深","花和尚");        HeroNode2 heroNode3 = new HeroNode2(3,"李逵","黑旋风");        HeroNode2 heroNode4 = new HeroNode2(4,"林冲","豹子头");        HeroNode2 heroNode5 = new HeroNode2(5,"公孙胜","入云龙");        //创建双向链表对象        HeroManagement2 heroes = new HeroManagement2();        //添加无序        heroes.add(heroNode3);        heroes.add(heroNode1);        heroes.add(heroNode4);        heroes.add(heroNode2);        //遍历        System.out.println("添加后遍历：");        heroes.list();        //修改        HeroNode2 changeHeroNode = new HeroNode2(3,"李逵111","黑旋风111");        heroes.update(changeHeroNode);        System.out.printf("修改no=%d后遍历：\n",changeHeroNode.no);        heroes.list();        //删除        heroes.del(3);        heroes.del(1);        System.out.println("删除1,3号后遍历：");        heroes.list();    }}//定义HeroManagement，管理我们的英雄class HeroManagement2 {    //初始化头节点，头结点不要动，不存放数据    private HeroNode2 head = new HeroNode2(0, "", "");    public HeroNode2 getHead() {        return head;    }    //1.遍历    public void list() {        //判断链表是否为空        if (head.next == null) {            System.out.println("链表为空~~~");            return;        }        //辅助temp来遍历        HeroNode2 temp = head.next;        while (true) {            if (temp == null) { //判断链表到最后                break;            }            System.out.println(temp);   //打印            temp = temp.next;   //指向下一个节点        }    }    //2.1添加  思路(不考虑编号顺序)：添加到最后一个节点的后面    public void add(HeroNode2 heroNode) {        //head节点不能动，用辅助遍历temp        HeroNode2 temp = head;  //临时存放头节点        while (true) {            if (temp.next == null) {    //找到链表的最后                break;            }            temp = temp.next;   //没找到temp后移        }        temp.next = heroNode;   //新的节点地址给最后一个节点的next        heroNode.pre = temp;    //最后节点的地址给新节点的pre    }    //3.修改    public void update(HeroNode2 newHeroNode) {        if (head.next == null) {    //判断是否为空            System.out.println("链表为空~");            return;        }        HeroNode2 temp = head.next;   //辅助变量        boolean flag = false;   //标志是否找到        while (true) {            if (temp.next  == null) {       //到了链表最后，没有找到同 no                break;            }            if (temp.no == newHeroNode.no) {  //找到no相同的temp                flag = true;                break;            }            temp = temp.next;        }        if (flag) { //找到了            temp.name = newHeroNode.name;            temp.nickname = newHeroNode.nickname;        } else {    //没找到            System.out.printf("没有找到要修改的no=%d的节点。",newHeroNode.no);        }    }    //4.删除    public void del(int no){        //判断为空        if (head.next == null) {            System.out.println("链表为空，不能删除~");            return;        }        HeroNode2 temp = head.next;   //辅助变量        boolean flag = false;   //标志是否找到        while (true){            if (temp ==null){  //到链表最后也没找到                break;            }            if (temp.no == no){    //找到了，temp是找到的前一个节点                flag = true;                break;            }            temp = temp.next;        }        if (flag){            temp.pre.next = temp.next;  //next            if (temp.next != null) {    //pre                temp.next.pre = temp.pre;   //假如删除的是最后一个节点 temp.next == null            }        } else {            System.out.printf("没有找到要删除的节点no=%d。\n",no);        }    }}class HeroNode2 {    //变量    public int no; //英雄编号    public String name; //英雄名字    public String nickname; //英雄昵称    public HeroNode2 next;  //下一个节点地址    public HeroNode2 pre;   //前一个节点地址    //构造器    public HeroNode2(int no, String name, String nickname) {        this.no = no;        this.name = name;        this.nickname = nickname;    }    //为了显示方便，重新toString    @Override    public String toString() {        return "HeroNode2{" +                "no=" + no +                ", name='" + name + '\'' +                ", nickname='" + nickname + '\'' +                '}';    }}

测试结果：

5) 作业：添加(按照编号添加)

代码：

package com.jiao.dataStructure;public class DoubleLinkedList {    public static void main(String[] args) {        //先创建节点数据        HeroNode2 heroNode1 = new HeroNode2(1,"宋江","及时雨");        HeroNode2 heroNode2 = new HeroNode2(2,"鲁智深","花和尚");        HeroNode2 heroNode3 = new HeroNode2(3,"李逵","黑旋风");        HeroNode2 heroNode4 = new HeroNode2(4,"林冲","豹子头");        HeroNode2 heroNode5 = new HeroNode2(5,"公孙胜","入云龙");        //创建双向链表对象        HeroManagement2 heroes = new HeroManagement2();        //添加有序        heroes.addByOrder(heroNode3);        heroes.addByOrder(heroNode1);        heroes.addByOrder(heroNode4);        heroes.addByOrder(heroNode2);        heroes.addByOrder(heroNode1);        heroes.addByOrder(heroNode5);        //遍历        System.out.println("添加后遍历：");        heroes.list();        //修改        HeroNode2 changeHeroNode = new HeroNode2(3,"李逵111","黑旋风111");        heroes.update(changeHeroNode);        System.out.printf("修改no=%d后遍历：\n",changeHeroNode.no);        heroes.list();        //删除        heroes.del(3);        heroes.del(1);        System.out.println("删除1,3号后遍历：");        heroes.list();    }}//定义HeroManagement，管理我们的英雄class HeroManagement2 {    //初始化头节点，头结点不要动，不存放数据    private HeroNode2 head = new HeroNode2(0, "", "");    public HeroNode2 getHead() {        return head;    }...    //2.2添加 按照编号顺序    public void addByOrder(HeroNode2 heroNode) {        HeroNode2 temp = head;   //临时变量存放头指针        HeroNode2 next = null; //存放temp的下一个节点        boolean flag = false;   //是否重复的标志        while (true) {            if (temp.next == null) {    //找到了最后                break;            }            if (temp.next.no > heroNode.no) {   //temp.next的no开始大于要插入的no,说明当前的temp找到了                break;            } else if ( temp.next.no == heroNode.no) {  //要添加的no在链表存在了                flag = true;                break;            }            temp = temp.next;        }        //2.通过flag,判定添加        if (flag) {            System.out.printf("准备插入的英雄编号:%d已经存在,不能添加！\n",heroNode.no);        } else {            next = temp.next;   //改变temp前先保存.next值            //连接前一个            temp.next = heroNode;            heroNode.pre = temp;            //连接后一个            heroNode.next = next;            if (next != null) {                next.pre = heroNode;            }        }    }}class HeroNode2 {...}

测试结果：

单向环形链表（Josephu约瑟夫问题）

Josephu(约瑟夫)问题：

设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数， 数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推， 直到所有人出列为止，由此产生一个出队编号的序列。

提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

假设：n=5有五个人,k=1从第一个开始报数,m=2数两下， 出队列的顺序：2->4->1->5->3

思路：

构建一个单向的环形链表思路：

• 1) 先创建第一个节点，让first指向该节点，并形成环状；
• 2) 后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中。

遍历环形链表：

• 1) 先让一个辅助指针(变量)curBoy，指向first节点；
• 2) 然后通过一个while循环遍历 该环形链表即可curBoy.next=first。

代码段：

package com.jiao.dataStructure;public class Josephu {    public static void main(String[] args) {        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();        //新建5个节点        circleSingleLinkedList.addBoy(5);        //输出节点        circleSingleLinkedList.showBoy();    }}//创建一个单向环形链表class CircleSingleLinkedList {    //创建一个first节点，无编号    Boy first = new Boy(-1);    //添加节点，构建一个环形的链表,nums表示添加节点个数    public void addBoy(int nums) {        //nums数据校验        if (nums < 1){//至少添加1个节点            System.out.println("添加的节点个数不对~");            return;        }        //curBoy辅助指针，帮助我们构建环形链表        Boy curBoy = null;        //for循环来创建我们的环形链表        for (int i = 1; i <= nums; i++) {            //根据编号创建节点            Boy boy = new Boy(i);            //编号为1的节点            if (i == 1) {                first = boy;    //给新建的first节点赋值                first.setNext(first);   //自己指向自己                curBoy = first;   // 变量位置            } else {                curBoy.setNext(boy);    //curBoy.next指向新加的boy                boy.setNext(first);     //新加的boy指向first节点                curBoy = boy;   //curBoy 后移            }        }    }    //遍历当前的环形链表    public void showBoy() {        //判断是否为空        if (first == null) {            System.out.println("当前环形链表没有节点~");            return;        }        //因为first不能动，所以变量curBoy辅助指针        Boy curBoy = first;        while (true) {            System.out.printf("节点的编号为:%d\n",curBoy.getNo());            if (curBoy.getNext() == first) {    //遍历完了                break;            }            curBoy = curBoy.getNext();  //curBoy后移        }    }}//创建一个Boy类，表示一个节点class Boy {    private int no;     //编号    private Boy next;   //指向下一个节点，默认null    public Boy(int no) {        this.no = no;    }...geter和seter省略}

测试结果：

节点出圈：

• 1) 需求创建一个辅助指针(变量)helper,事先应该指向环形链表的最后这个节点 。 补充：报数前，先让first和helper移动k-1次
• 2) 当报数的时候，让first和helper指针同时的移动m-1次[自己要算一次]
• 3) 这时就可以将first指向的小孩出圈。 first = first.next。 helper.next = first。 原来的first指向的节点就没有任何引用，就会被回收

package com.jiao.dataStructure;public class Josephu {    public static void main(String[] args) {        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();        //新建5个节点        circleSingleLinkedList.addBoy(5);        //出圈        circleSingleLinkedList.countBoy(1,2,5);    }}//创建一个单向环形链表class CircleSingleLinkedList {    //创建一个first节点，无编号    Boy first = new Boy(-1);...    //根据用户的输入，计算出小孩出圈的顺序    /**     *     * @param startNo   表示从第几个小孩开始数数     * @param countNum  表示表示数几下     * @param nums      表示最初有几个小孩在圈里     */    public void countBoy(int startNo, int countNum, int nums) {        //先对数据进行校验        if (first == null || startNo < 1 || startNo > nums) {            System.out.println("参数输入有误~");            return;        }        //创建辅助指针，帮助出圈helper        Boy helper = first;        while (true) {            if (helper.getNext() == first) {                break;            }            helper = helper.getNext();        }        //移动到指定位置k-1次        for (int i = 0; i < startNo - 1; i++) {            first = first.getNext();            helper = helper.getNext();        }        //出圈(先移动再出圈)        while (true) {            if (helper == first) {  //最后一个退出                break;            }            //类似于移动的"步长"            for (int j = 0; j < countNum - 1; j++) {                first = first.getNext();    //当前要删除的节点                helper = helper.getNext();  //当前要删除节点的前一个节点            }            System.out.printf("当前出圈的序号是:%d\n",first.getNo());            //删除当前节点            first = first.getNext();    //当前节点后移一位            helper.setNext(first);      //当前要删除的节点的前一个节点(helper)指向当前删除的节点的后一个节点        }        System.out.printf("最后一个出圈的的序号是:%d",first.getNo());        //System.out.printf("最后一个出圈的的序号是:%d",helper.getNo()); 一样的    }}//创建一个Boy类，表示一个节点class Boy {...}

测试结果：