链表
一、单向链表
1、基本介绍
1. 链表是有序的列表，但是他再内存中的存储如下 ----------->
2. 链表是以节点的方式来存储数据的，是链式存储
3. 每个节点包含data域（存数据） next域（存下一个节点的地址）
4. 链表中各个节点不一定是连续存储。（可以充分利用碎片内存）
5. 链表分为 带头节点链表 和 不带头节点链表，根据实际需求来确定
2、带头节点的链表
1. head节点不存放任何具体数据，作用就是表示单链表的头。
2. 最后一个节点的next域 存放的是null，表示这是尾部
3. 从单项链表中添加一个节点的思路
• 直接在添加时添加到链表的尾部
• 首先判断链表是否为空 head.next == null
• 创建一个temp辅助变量，temp = head
• 遍历时 如果当 temp.next = null, 说明跳出循环，进行添加 temp.next = 新节点
• 每循环一次，temp向后移动一位
• 根据id的大小，按顺序添加到链表中
• 首先判断是否链表是否为空
• 需要一个temp辅助变量 temp = head
• 首先需要搞清楚，如果 现在链表中有 1 3 两个节点，你需要将2 添加进去
• 在循环中 如果 temp.next.id > 新节点.id 则表示可以将节点插入到 temp 和 temp.next 之间，break;退出循环
• 使用一个辅助变量 flag ，表示id是重复，就给赋值上true
• 在循环中，如果temp.next.id == 新节点.id 则表示id重复，不能进行插入 falg = true
• 每循环一次，temp向后移动一位
• 判断如果为false 就给插入 //2.next = 1.next; 1.next = 2; 这样 2 就被插入到 1 和 3的中间了
• 如果是true 给出提示信息，表示id重复
4. 根据id更新一个节点的数据，不更新 id 和 next ，其余都可以更新 的思路
• 先遍历 (遍历前先判断链表是否为空)
• 在循环中 判断 if（temp.next.id == 新节点.id) 找到了就退出循环
• 没循环一次 temp就往后移动一位
• 可以使用一个flag变量 来根据变量判断 是否找到了 如果为true则更新 为false表示没找到
5. 删除节点思路
• 我们先找到需要删除的这个节点的 前面一个节点 temp
• 然后 temp.next = temp.next.next 这样就删除了中间的那个节点
• 举例：1 2 3 个节点，1的下一个节点是 1.next.next 则 1.next = 3 ，这样2 就没了
• 被删除的节点没有了其他引用的指向，会被垃圾回收器机制回收
二、单项链表代码实现
package com.yixuexi.linkedList;
import java.util.Stack;
/**
* 2020/10/10 20:10
*/
//模拟带头节点的单向链表
public class HeadLinkedListDemo {
public static void main(String[] args) {
//进行测试
//首先创建几个人物数据
HeroNode n1 = new HeroNode(1,"松江","及时雨");
HeroNode n2 = new HeroNode(2,"李逵","黑旋风");
HeroNode n3 = new HeroNode(3,"吴用","智多星");
HeroNode n4 = new HeroNode(4,"卢俊义","玉麒麟");
HeroNode n5 = new HeroNode(5,"武大郎","烧饼哥");
//创建一个链表
HeadLinkedList headLinkedList = new HeadLinkedList();
//往链表中添加数据
headLinkedList.add(n1);
headLinkedList.add(n2);
headLinkedList.add(n5);
//查看链表中的数据
headLinkedList.list();
//往链表中添加数据
headLinkedList.addByOrder(n3);
headLinkedList.addByOrder(n4);
headLinkedList.addByOrder(n4);
//分割线
System.out.println("------------------------------------------------->");
//再次查看链表中的数据
headLinkedList.list();
//分割线
System.out.println("------------------------------------------------->");
//更新链表中的数据
HeroNode newn5 = new HeroNode(5,"武松","打虎哥");
HeroNode newn6 = new HeroNode(6,"武松","打虎哥");
headLinkedList.update(newn5);
headLinkedList.update(newn6);
//再次查看链表中的数据
headLinkedList.list();
//分割线
System.out.println("------------------------------------------------->");
//删除链表中的数据
headLinkedList.delete(2);
//查看删除之后的数据
headLinkedList.list();
//查看链表中有效数据的个数
System.out.println(HeadLinkedList.getLength(headLinkedList.getHead()));
//查看链表中倒数第2个节点
HeroNode last = HeadLinkedList.getLast(headLinkedList.getHead(), 2);
System.out.println(last);
//分割线
System.out.println("------------------------------------------------->");
//反转链表
//HeadLinkedList.reverse(headLinkedList.getHead());
//headLinkedList.list();
//分割线
System.out.println("------------------------------------------------->");
// 反向打印链表
HeadLinkedList.reversePrint(headLinkedList.getHead());
}
}
//创建一个单向链表类，用来管理单项链表
class HeadLinkedList {
//在这个单项链表类中有一个 头节点，这个头节点不能动
private HeroNode head = new HeroNode(0, "", "");
public HeroNode getHead() {
return head;
}
/**
* 此方法 添加数据的时候没有顺序，是按照先添加的在前面，后添加的在后面的顺序
*
* @param heroNode
*/
public void add(HeroNode heroNode) {
//由于每次添加节点都是往链表的最后去添加，所以先要遍历一遍链表，找出最后那个元素
//这里遍历我们使用一个 temp临时变量 辅助我们遍历
//这里这个temp就是头节点，使用循环，如果temp.next == null，则表示它是最后一个节点
//如果 temp.next != null 则表示它不是最后一个节点，则往后移一位， temp = temp.next;
HeroNode temp = head;
while (true) {
if (temp.next == null) {
//说明此时 temp是最后一个节点 直接跳出循环
break;
}
//能执行到这里，则表示不是最后一个节点，往后移动一位，继续循环
temp = temp.next;
}
//执行到这里，说明此时的temp一定为最后一个节点，直接将节点添加到 temp.next 即可
temp.next = heroNode;
}
/**
* 按照id的顺序进行添加
* 添加的时候按照数据 的id 进行排序，id 为 1 的在空节点后面 1 ->> 2 ->> 3 ->> 4
*/
public void addByOrder(HeroNode heroNode) {
//假设：现在链表中的数据为 1 3 4
//现在 需要将2 插入到 1 和 3 的中间去
//因为头节点不能动，所以需要一个temp辅助变量 来帮助我们遍历
HeroNode temp = head;
//需要使用一个flag辅助我们 判断是否插入的数据id已经存在了
Boolean flag = false;
//首先判断，如果这个链表为空，则直接添加在链表的后面即可
if (temp.next == null) {
temp.next = heroNode;
return;
}
//循环 找到插入数据的位置 假设 将 2 插入到 1 3 中间
// 则 2.next = 1.next; 1.next = 2; 这样 2 就被插入到 1 和 3的中间了
while (true) {
//这样则表示需要插入的位置找到了，就在 temp 和 temp.next 的中间
if (temp.next.id > heroNode.id) {
break;
} else if (temp.next.id == heroNode.id) { //表示插入的数据id在链表中已经存在了
flag = true;
break;
}
//如果上面都没有实现则 temp向后移动一位
temp = temp.next;
}
// 将节点插入到指定位置 temp 和 temp.next之间
if (flag) {
System.out.println("你要添加节点的id已经存在 id = " + heroNode.id + " 无法添加");
} else {
// 则 2.next = 1.next; 1.next = 2; 这样 2 就被插入到 1 和 3的中间了
heroNode.next = temp.next;
temp.next = heroNode;
}
}
/**
* 根据id 对节点的姓名和绰号进行更新
*
* @param newHeroNode
*/
public void update(HeroNode newHeroNode) {
//需要使用一个辅助变量 temp
HeroNode temp = head;
//首先判断是否为空，如果为空直接退出
if (temp.next == null) {
System.out.println("链表为空，请加入节点后在进行更新！");
return;
}
//使用循环找出id为 newHeroNode.id 的节点
Boolean flag = false;
while (true) {
if (temp == null) {
break;
}
//如果找到了 那么直接跳出循环，因为当前temp 就是需要修改的节点
if (temp.id == newHeroNode.id) {
flag = true;
break;
}
//没有找到则向后移动一位
temp = temp.next;
}
//判断 如果flag为true 则表示当前temp是需要修改的
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else {
System.out.println("没有找到对应id的节点，请输入正确的数据");
}
}
//删除节点
public void delete(int id) {
//辅助变量
HeroNode temp = head;
// 标记
boolean flag = false;
//思路：找到要删除的节点的前面那个 节点 temp
//然后 temp.next = temp.next.next 这样中间那个节点的指向就没了，垃圾回收器就回收了
while (true) {
if (temp.next == null) {
return;
}
if (temp.next.id == id) {
flag = true;
break;
}
// 如果都没有 则向后移动一位
temp = temp.next;
}
if (flag) {
temp.next = temp.next.next;
} else {
System.out.println("没有找到对应的节点id ： " + id);
}
}
//用来展示链表中的数据
public void list() {
//使用一个temp辅助变量来帮助我们进行循环遍历
HeroNode temp = head;
//首先判断一下这个链表是否为空链表
//如果头节点的next域 为空则表示没有下一个节点，为空链表
if (temp.next == null) {
return;
}
// 因为上面做了判断了，所以直接输出就行
//然后把temp往后移动一位，如果temp.next为空，则表示到头了
while (true) {
System.out.println(temp.next);
temp = temp.next;
if (temp.next == null) {
break;
}
}
}
//用来查看链表中有效数据的个数
//传过来一个头节点，即可得到他的长度
public static int getLength(HeroNode head){
//判断如果这个链表是空链表的话 直接return 0 就行
if (head.next == null){
return 0;
}
//因为不算上 头节点，所以是 head.next
HeroNode temp = head.next;
int length = 0;
while ( temp != null){
length ++;
temp = temp.next;
}
return length;
}
//用来查看链表中倒数第K个节点
public static HeroNode getLast(HeroNode head, int index){
//1.首先根据头节点 得到链表的长度
//判断如果这个链表是空链表的话 直接return 0 就行
if (head.next == null){
return null;
}
//因为不算上 头节点，所以是 head.next
HeroNode temp = head.next;
int length = 0;
while ( temp != null){
length ++;
temp = temp.next;
}
//2. 做一个数据的校验，判断index是否合理
if(index <= 0 || index > length){
return null;
}
//3. 进行遍历，倒数第几个 ： 长度 - 倒数第几个 = 要找的那个
HeroNode temp2 = head; //辅助变量，帮我们遍历
for(int i = 0; i <= length - index; i++){
if (temp2.next == null){
break;
}
temp2 = temp2.next;
}
return temp2;
}
//传入一个头节点，对其进行链表反转
public static void reverse(HeroNode head){
//如果链表为空 或者 链表中就一个元素，那么直接返回这个链表就行，不用反转
if (head.next == null || head.next.next == null){
return;
}
//定义一个辅助变量，帮助我们遍历链表
HeroNode cur = head.next;
//此变量永远指向 cur的下一个节点
HeroNode next = null;
//新的头节点
HeroNode reverseHead = new HeroNode(0,"","");
while (cur != null){
//保存cur的下一个节点，防止丢失
next = cur.next;
//将cur的下一个节点指向新的链表的最前端 右边的那条链子
cur.next = reverseHead.next;
//头插法，将每一个遍历的节点插入到链表的最前端 左边的那条链子
reverseHead.next = cur;
//向后移动一位
cur = next;
}
//将head.next 执行reverserHead.next 实现单链表的反转
head.next = reverseHead.next;
}
//从头到尾打印单链表，使用栈数据结构
public static void reversePrint(HeroNode head){
//先判断 链表是否为空。
if(head.next == null){
return;
}
Stack<HeroNode> stack = new Stack<>();
HeroNode temp = head.next;
while (temp != null){
//把节点压入栈中【先进后出】
stack.push(temp);
//向后移动一位
temp = temp.next;
}
//将栈中的节点进行打印,因为是先进后出，所以就完成了倒序打印
while (stack.size() > 0){
System.out.println(stack.pop());
}
}
}
//创建一个节点类
class HeroNode{
public int id;
public String name;
public String nickname;
public HeroNode next; //表示单向链表中的next区域，存放下一个节点
//构造器，
public HeroNode(int id, String name, String nickname) {
this.id = id;
this.name = name;
this.nickname = nickname;
}
//重写toString的时候 next不需要重写
@Override
public String toString() {
return "HeroNode{" +
"id=" + id +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
三、单项链表面试题
1、求单项链表中有效节点的个数
（如果是带头节点的，不统计头节点）
//用来查看链表中有效数据的个数
//传过来一个头节点，即可得到他的长度
public static int getLength(HeroNode head){
//判断如果这个链表是空链表的话 直接return 0 就行
if (head.next == null){
return 0;
}
//因为不算上 头节点，所以是 head.next
HeroNode temp = head.next;
int length = 0;
while ( temp != null){
length ++;
temp = temp.next;
}
return length;
}
调用：
System.out.println(HeadLinkedList.getLength(headLinkedList.getHead()));
2、查找单链表中的单数第K个节点【新浪面试题】
2.1 思路：
1. 编写一个方法，接收 head节点，同时接收一个index
2. index 是表示倒数第几个节点
3. 先把链表从头到尾遍历一遍，得到长度
4. 得到长度之后，我们从链表的第一个开始遍历（size - index）个，就可以得到了
2.2 代码实现
//用来查看链表中倒数第K个节点
public static HeroNode getLast(HeroNode head, int index){
//1.首先根据头节点 得到链表的长度
//判断如果这个链表是空链表的话 直接return 0 就行
if (head.next == null){
return null;
}
//因为不算上 头节点，所以是 head.next
HeroNode temp = head.next;
int length = 0;
while ( temp != null){
length ++;
temp = temp.next;
}
//2. 做一个数据的校验，判断index是否合理
if(index <= 0 || index > length){
return null;
}
//3. 进行遍历，倒数第几个 ： 长度 - 倒数第几个 = 要找的那个
HeroNode temp2 = head; //辅助变量，帮我们遍历
for(int i = 0; i <= length - index; i++){
if (temp2.next == null){
break;
}
temp2 = temp2.next;
}
return temp2;
}
3、单链表的反转【腾讯面试题】
3.1 思路：
1. 先定义一个新的节点，HeroNode reverseHead = new HeroNode();
2. 从头到尾遍历节点，将每一个遍历的节点放到头的后面 【头插法】
• 这样就是 1 2 3 先插入1， 然后 在往1之前插入2 在往2 之前插入3
3. 原来链表head.next = reverseHead.next;
3.2 代码实现【头插法】
//传入一个头节点，对其进行链表反转
public static void reverse(HeroNode head){
//如果链表为空 或者 链表中就一个元素，那么直接返回这个链表就行，不用反转
if (head.next == null || head.next.next == null){
return;
}
//定义一个辅助变量，帮助我们遍历链表
HeroNode cur = head.next;
//此变量永远指向 cur的下一个节点
HeroNode next = null;
//新的头节点
HeroNode reverseHead = new HeroNode(0,"","");
while (cur != null){
//保存cur的下一个节点，防止丢失
next = cur.next;
//将cur的下一个节点指向新的链表的最前端 右边的那条链子
cur.next = reverseHead.next;
//头插法，将每一个遍历的节点插入到链表的最前端 左边的那条链子
reverseHead.next = cur;
//向后移动一位
cur = next;
}
//将head.next 执行reverserHead.next 实现单链表的反转
head.next = reverseHead.next;
}
4、从尾到头打印单链表【百度面试题，要求：1.反向遍历，2。Stack栈】
4.1 思路
• 思路1：将单链表反转过来，然后再打印【问题：会破坏原来链表的结构】
• 思路2：利用栈数据结构，将各个节点压入栈中，利用栈的先进后出的特点 就实现了逆序打印的效果
4.2 代码实现：
//从头到尾打印单链表，使用栈数据结构
public static void reversePrint(HeroNode head){
//先判断 链表是否为空。
if(head.next == null){
return;
}
Stack<HeroNode> stack = new Stack<>();
HeroNode temp = head.next;
while (temp != null){
//把节点压入栈中【先进后出】
stack.push(temp);
//向后移动一位
temp = temp.next;
}
//将栈中的节点进行打印,因为是先进后出，所以就完成了倒序打印
while (stack.size() > 0){
System.out.println(stack.pop());
}
}
5、合并两个有序的单链表，合并之后的链表依然有序
四、双向链表
1、双向链表和单向链表有什么不一样的地方
• 除了有data域，next域，还有一个pre域 用来保存前一个节点。
• head头部也有pre域，可以向头部的前面加节点
2、分析双向链表的遍历，增加，删除，修改。
2.1遍历思路：
• 遍历跟单链表一样，只是可以向前，也可以向后查找
2.2 添加思路：(添加到链表的最后)
• 先找到双向链表的最后那个节点
• 先让 temp.next = 新节点
• 然后 新节点.pre = temp
2.3 修改思路：
• 和原来的单项链表一致，先找到节点再修改
2.4 删除思路：
• 因为是双向链表，所以不需要找到 删除的前一个节点，直接找到要删除的节点就行
• 然后 要删除的节点.pre.next = 要删除的节点.next;
• 再然后 要删除的节点.next.pre = 要删除的节点.pre
• 需要注意的是如果是删除最后一个节点的话，就不需要最后一句了，所以加一个if判断
五、双向链表代码实现
package com.yixuexi.linkedList;
/**
* 2020/10/11 20:57
*/
public class DoubleLinkedListDemo {
public static void main(String[] args) {
//进行测试
//首先创建几个人物数据
DoubleHeroNode n1 = new DoubleHeroNode(1,"松江","及时雨");
DoubleHeroNode n2 = new DoubleHeroNode(2,"李逵","黑旋风");
DoubleHeroNode n3 = new DoubleHeroNode(3,"吴用","智多星");
DoubleHeroNode n4 = new DoubleHeroNode(4,"卢俊义","玉麒麟");
DoubleHeroNode n5 = new DoubleHeroNode(5,"武大郎","烧饼哥");
//创建链表
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.add(n1);
doubleLinkedList.add(n2);
doubleLinkedList.add(n3);
doubleLinkedList.add(n4);
doubleLinkedList.add(n5);
//查看链表中的数据
doubleLinkedList.list();
//删除表中的数据
doubleLinkedList.delete(1);
doubleLinkedList.delete(5);
System.out.println("-------------------------------->");
//查看链表中的数据
doubleLinkedList.list();
DoubleHeroNode n6 = new DoubleHeroNode(5,"潘金莲","烧饼哥老婆");
doubleLinkedList.update(n6);
System.out.println("-------------------------------->");
//查看链表中的数据
doubleLinkedList.list();
}
}
//
class DoubleLinkedList{
//在这个单项链表类中有一个 头节点，这个头节点不能动
private DoubleHeroNode head = new DoubleHeroNode(0, "", "");
public DoubleHeroNode getHead() {
return head;
}
//遍历的方法
//用来展示链表中的数据
public void list() {
//使用一个temp辅助变量来帮助我们进行循环遍历
DoubleHeroNode temp = head;
//首先判断一下这个链表是否为空链表
//如果头节点的next域 为空则表示没有下一个节点，为空链表
if (temp.next == null) {
return;
}
// 因为上面做了判断了，所以直接输出就行
//然后把temp往后移动一位，如果temp.next为空，则表示到头了
while (true) {
System.out.println(temp.next);
temp = temp.next;
if (temp.next == null) {
break;
}
}
}
//用来添加节点的方法【从链表的尾部添加】
public void add(DoubleHeroNode doubleHeroNode) {
//由于每次添加节点都是往链表的最后去添加，所以先要遍历一遍链表，找出最后那个元素
//这里遍历我们使用一个 temp临时变量 辅助我们遍历
//这里这个temp就是头节点，使用循环，如果temp.next == null，则表示它是最后一个节点
//如果 temp.next != null 则表示它不是最后一个节点，则往后移一位， temp = temp.next;
DoubleHeroNode temp = head;
while (true) {
if (temp.next == null) {
//说明此时 temp是最后一个节点 直接跳出循环
break;
}
//能执行到这里，则表示不是最后一个节点，往后移动一位，继续循环
temp = temp.next;
}
//执行到这里，说明此时的temp一定为最后一个节点，直接将节点添加到 temp.next 然后把添加的元素.pre = temp
temp.next = doubleHeroNode;
doubleHeroNode.pre = temp;
}
//删除元素的方法
public void delete(int index){
DoubleHeroNode temp = head;
boolean flag = false;
while (true){
if (temp == null){
return;
}
if (temp.id == index){
flag = true;
break;
}
temp = temp.next;
}
if (flag){
temp.pre.next = temp.next;
//这里代码有问题，如果是删除的最后一个节点的话会报出空指针异常,所以需要加上if判断
if (temp.next != null){
temp.next.pre = temp.pre;
}
}else{
System.out.println("没有找到你要删除的节点");
}
}
public void update(DoubleHeroNode doubleHeroNode){
//需要使用一个辅助变量 temp
DoubleHeroNode temp = head;
//首先判断是否为空，如果为空直接退出
if (temp.next == null) {
System.out.println("链表为空，请加入节点后在进行更新！");
return;
}
//使用循环找出id为 newHeroNode.id 的节点
Boolean flag = false;
while (true) {
if (temp == null) {
break;
}
//如果找到了 那么直接跳出循环，因为当前temp 就是需要修改的节点
if (temp.id == doubleHeroNode.id) {
flag = true;
break;
}
//没有找到则向后移动一位
temp = temp.next;
}
//判断 如果flag为true 则表示当前temp是需要修改的
if (flag) {
temp.name = doubleHeroNode.name;
temp.nickname = doubleHeroNode.nickname;
} else {
System.out.println("没有找到对应id的节点，请输入正确的数据");
}
}
}
//创建一个有着双向节点的类
class DoubleHeroNode {
public int id;
public String name;
public String nickname;
public DoubleHeroNode next; //表示双向链表中的next区域，存放下一个节点
public DoubleHeroNode pre; //表示双向链表中的pre区域，存放上一个节点
//构造器，
public DoubleHeroNode(int id, String name, String nickname) {
this.id = id;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "DoubleHeroNode{" +
"id=" + id +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
六、单向环形链表
1、单向环形链表应用场景
约瑟夫问题：
Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
假设：
n = 5 表示有几个人
k = 1 表示从第1个人 开始报数
m = 2 表示数两下【自身是1下，第二下那个人出列】然后第三个人数
最后出队列的顺序是 2->4->1->5->3
解决方案：使用单向环形链表，没有头节点，最后一个节点指向第一个节点
2、创建环形链表的思路
• 先创建第一个节点，让first节点指向该节点，这样就形成了环状
• 后面当我们没创建一个新的节点，就把该节点加入到以后的环形链表中即可。
3、遍历环形链表的思路
• 让一个辅助变量 curboy，指向first节点，
• 然后通过一个while循环进行遍历
• 再循环中 如果curboy.next = first 则可以break了，因为 前遍历的下一个节点是 第一个节点 则表示遍历完了
4、约瑟夫问题思路
约瑟夫问题代码实现
package com.yixuexi.linkedList;
/**
* 2020/10/12 19:20
*/
/*解决约瑟夫问题，模拟环形链表*/
public class Josepfu {
public static void main(String[] args) {
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5);
circleSingleLinkedList.showBoy();
circleSingleLinkedList.countBoy(1,2,5);
}
}
class CircleSingleLinkedList{
//创建一个 first 指针，这个指针永远指向 第一个节点。
public Boy first = null;
//创建环形链表
public void addBoy(int nums){
//首先判断传进来的值合不合法，如果说构建一个小于1 个环形链表 那完全没必要
if (nums < 1){
System.out.println("构建链表节点数量太少，没必要！");
return;
}
//创建一个辅助指针，帮助我们创建环形链表
Boy curBoy = null;
//进行构建
for (int i = 1; i <= nums; i ++){
//每循环一次，创建一个小孩
Boy boy = new Boy(i);
//如果是创建第一个小孩，那么这时第一个节点，让first指向这个第一个节点
if ( i == 1 ){
first = boy;
//再将first的下一个节点指向boy，形成一个环
first.setNext(boy);
//让辅助节点指向first
curBoy = first;
}else{
//倒数第二个节点的next 指向倒数第一个节点
curBoy.setNext(boy);
//将最后一个节点指向第一个节点，形成一个环
boy.setNext(first);
//向后一位移动
curBoy = boy;
}
}
}
//遍历当前的单项环形链表
public void showBoy(){
if (first == null){
System.out.println("空链表，没有必要做遍历");
return;
}
Boy curBoy = first;
while (true){
System.out.println("小孩的编号为：" + curBoy.getNo());
//因为是环形链表，所以说 如果当前遍历的下一个节点是 第一个节点 则表示遍历完了
if (curBoy.getNext() == first){
break;
}
//向后移动一位
curBoy = curBoy.getNext();
}
}
// 根据用户的输入，计算出小孩出圈的顺序
/**
*
* @param starNo 表示从第几个小孩开始数
* @param countNum 表示数几下
* @param nums 表示最初有几个小孩在圈中
*/
public void countBoy(int starNo,int countNum, int nums){
//先对数据进行一波校验
if (first == null || starNo < 1 || starNo > nums){
System.out.println("输入的参数有误，请重新输入");
return;
}
//创建辅助节点，帮助完成小孩出圈
Boy helper = first;
//将helper 移动到这个链表的最后一个节点
while (true){
if (helper.getNext() == first){
break;
}
//向后移动一位
helper = helper.getNext();
}
//在小孩报数前，先让first 和 helper移动 k-1 次
for (int j = 0; j < starNo - 1; j ++){
first = first.getNext();
helper = helper.getNext();
}
//当小孩报数时，让first和helper指针同时移动 m -1次，然后出圈
//通过循环，让这个链表中 到最后只剩下一个节点
while (true){
if (helper == first){
break;
}
//让first和helper同时的移动 countNum - 1
for (int i = 0; i < countNum -1 ; i++){
first = first.getNext();
helper = helper.getNext();
}
//此时的first 指向的就是要出圈小孩的节点，
System.out.println(first.getNo());
//将小孩出圈
first = first.getNext();
helper.setNext(first);
}
System.out.println("最后留在圈中的小孩的编号为 " + first.getNo());
}
}
//小孩节点
class Boy{
private int no; //小孩id
private Boy next;
public Boy(int no) {
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}