小结：
- 链表是以节点的方式来存储的，是链式存储
- 每个节点包含data域，next域：指向下一个节点。
- 链表的各个节点不一定是连续存储
- 链表分 带头节点 和 没带头节点的链表，根据实际的需求来确定
实际场景 ： 客户端给了服务器一串没有顺序的ID，服务器排序并返回，不能查数据库，就在内存层面完成
逻辑结构：
单链表单实例应用
添加&遍历 思路及实现
- 第一种方式，直接添加到尾部： ```java package com.cheung.linkedlist;
public class SingleLinkedListDemo { public static void main(String[] args) { //测试 //先创建几个节点 //创建一个列表 SingleLinkedList singleLinkedList = new SingleLinkedList(); //加入 singleLinkedList.add(new HeroNode(1,”宋江”,”及时雨”)); singleLinkedList.add(new HeroNode(2,”卢俊义”,”玉麒麟”)); singleLinkedList.add(new HeroNode(3,”唔用”,”智多星”)); singleLinkedList.add(new HeroNode(4,”林冲”,”豹子头”)); //显示 singleLinkedList.list(); } }
//定义SingleLinkedList 管理我们的英雄 class SingleLinkedList{ //先初始化一个头节点，头节点不要动 不存放具体的数据 private HeroNode head = new HeroNode(0,””,””);
//添加节点到单向链表//思路 当不考虑编号顺序时：1找到当前链表最后节点 2将最后这个节点的next 指向 新的节点public void add(HeroNode heroNode){//因为head节点不能动，因此我们需要一个辅助遍历tempHeroNode temp = head;//遍历链表找到最后while (true){// 找到链表的最后if(temp.next == null){break;}//如果没找到最后，就将temp后移temp = temp.next;}//当退出while循环时，temp就指向了链表的最后//将最后的这个节点的next指向新的节点temp.next = heroNode;}//显示链表 遍历public void list(){//判断链表是否为空if(head.next == null){System.out.println("链表为空");return;}//因为头节点不能动 所以我们需要一个辅助变量来遍历HeroNode temp = head.next;while (true){//判断是否到链表的最后if(temp == null){break;}//输出节点信息System.out.println(temp.toString());//将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;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}
- 第二种方式，插入指定位置
<br />addByOrder 这样虽然我们没按顺序插入，但是是按顺序给我们排的<br />在内存层面就给我们排好了
```java
package com.cheung.linkedlist;
public class SingleLinkedListDemo {
public static void main(String[] args) {
//测试
//先创建几个节点
//创建一个列表
SingleLinkedList singleLinkedList = new SingleLinkedList();
//加入
// singleLinkedList.add(new HeroNode(1,"宋江","及时雨"));
// singleLinkedList.add(new HeroNode(2,"卢俊义","玉麒麟"));
// singleLinkedList.add(new HeroNode(3,"唔用","智多星"));
// singleLinkedList.add(new HeroNode(4,"林冲","豹子头"));
//加入 按照编号
singleLinkedList.addByOrder(new HeroNode(1,"宋江","及时雨"));
singleLinkedList.addByOrder(new HeroNode(4,"林冲","豹子头"));
singleLinkedList.addByOrder(new HeroNode(2,"卢俊义","玉麒麟"));
singleLinkedList.addByOrder(new HeroNode(3,"唔用","智多星"));
singleLinkedList.addByOrder(new HeroNode(4,"林冲","豹子头"));
//显示
singleLinkedList.list();
}
}
//定义SingleLinkedList 管理我们的英雄
class SingleLinkedList{
//先初始化一个头节点，头节点不要动 不存放具体的数据
private HeroNode head = new HeroNode(0,"","");
//添加节点到单向链表
//思路 当不考虑编号顺序时：1找到当前链表最后节点 2将最后这个节点的next 指向 新的节点
public void add(HeroNode heroNode){
//因为head节点不能动，因此我们需要一个辅助变量遍历temp
HeroNode temp = head;
//遍历链表找到最后
while (true){
// 找到链表的最后
if(temp.next == null){
break;
}
//如果没找到最后，就将temp后移
temp = temp.next;
}
//当退出while循环时，temp就指向了链表的最后
//将最后的这个节点的next指向新的节点
temp.next = heroNode;
}
//第二种方式 在添加英雄时，根据排名将英雄插入到指定位置
// （如果有这个排名，则添加失败，并给出提示）
public void addByOrder(HeroNode heroNode){
//因为head节点不能动，因此我们需要一个辅助指针遍历temp
//因为是单链表，因为我们找的temp是位于添加位置的前一个节点，否则插入不了
HeroNode temp = head;
boolean flag = false; //标识添加的编号是否存在，默认为false
while (true){
if(temp.next == null){//说明temp已经在链表的最后了
break; //不管找到没找到 都到最后了
}
if(temp.next.no > heroNode.no){ //位置找到了，就在temp的后面插入就行
break;
}else if(temp.next.no == heroNode.no){ //说明编号已经存在，不能插入
flag = true; //说明编号存在
break;
}
temp = temp.next; //后移，遍历当前列表
}
if(flag){
System.out.println("不能添加，编号已经存在\n" + heroNode.no);
}else {
//插入
heroNode.next = temp.next;
temp.next = heroNode;
}
}
//显示链表 遍历
public void list(){
//判断链表是否为空
if(head.next == null){
System.out.println("链表为空");
return;
}
//因为头节点不能动 所以我们需要一个辅助变量来遍历
HeroNode temp = head.next;
while (true){
//判断是否到链表的最后
if(temp == null){
break;
}
//输出节点信息
System.out.println(temp.toString());
//将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;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}
修改 思路及实现
//修改节点的信息，根据编号来修改，并且编号不能修改
//说明
//1 根据newHeroNode的编号来修改即可
public void update(HeroNode newHeroNode){
//判断是否为空
if(head.next == null){
System.out.println("链表为空");
return;
}
//找到要修改的节点，根据no编号
//定义一个辅助变量
HeroNode temp = head.next;
boolean flag = false; //表示是否找到该节点
while(true){
if(temp == null){
break; //已经遍历完链表了
}
if(temp.no == newHeroNode.no){
//找到了
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.name = newHeroNode.name;
temp.nickName = newHeroNode.nickName;
}else {
System.out.println("没找到要修改的节点:" + newHeroNode.no);
}
}
测试一下 在主程序中
删除节点 思路&代码
//删除节点 按照编号
//我们在比较时，是temp.next.no和 需要删除的节点no比较
public void delete(int no){
//判断是否为空
if(head.next == null){
System.out.println("链表为空");
return;
}
//找到要删除的节点的前一个节点，根据no编号
//定义一个辅助变量
HeroNode temp = head;
boolean flag = false;
while (true){
if(temp.next == null){
break;
}
if(temp.next.no == no){
flag = true;
break;
}
temp = temp.next; //后移
}
if(flag){
temp.next = temp.next.next;
}else {
System.out.println("没找到指定的no：" + no);
}
}
记得测试一下
完整代码演示
package com.cheung.linkedlist;
public class SingleLinkedListDemo {
public static void main(String[] args) {
//测试
//先创建几个节点
//创建一个列表
SingleLinkedList singleLinkedList = new SingleLinkedList();
//加入
// singleLinkedList.add(new HeroNode(1,"宋江","及时雨"));
// singleLinkedList.add(new HeroNode(2,"卢俊义","玉麒麟"));
// singleLinkedList.add(new HeroNode(3,"唔用","智多星"));
// singleLinkedList.add(new HeroNode(4,"林冲","豹子头"));
//加入 按照编号
singleLinkedList.addByOrder(new HeroNode(1,"宋江","及时雨"));
singleLinkedList.addByOrder(new HeroNode(4,"林冲","豹子头"));
singleLinkedList.addByOrder(new HeroNode(2,"卢俊义","玉麒麟"));
singleLinkedList.addByOrder(new HeroNode(3,"唔用","智多星"));
singleLinkedList.addByOrder(new HeroNode(4,"林冲","豹子头"));
//修改节点测试
singleLinkedList.update(new HeroNode(2,"小卢","小尾巴"));
//测试删除
singleLinkedList.delete(4);
singleLinkedList.delete(6);
singleLinkedList.delete(1);
//显示
singleLinkedList.list();
}
}
//定义SingleLinkedList 管理我们的英雄
class SingleLinkedList{
//先初始化一个头节点，头节点不要动 不存放具体的数据
private HeroNode head = new HeroNode(0,"","");
//添加节点到单向链表
//思路 当不考虑编号顺序时：1找到当前链表最后节点 2将最后这个节点的next 指向 新的节点
public void add(HeroNode heroNode){
//因为head节点不能动，因此我们需要一个辅助变量遍历temp
HeroNode temp = head;
//遍历链表找到最后
while (true){
// 找到链表的最后
if(temp.next == null){
break;
}
//如果没找到最后，就将temp后移
temp = temp.next;
}
//当退出while循环时，temp就指向了链表的最后
//将最后的这个节点的next指向新的节点
temp.next = heroNode;
}
//第二种方式 在添加英雄时，根据排名将英雄插入到指定位置
// （如果有这个排名，则添加失败，并给出提示）
public void addByOrder(HeroNode heroNode){
//因为head节点不能动，因此我们需要一个辅助指针遍历temp
//因为是单链表，因为我们找的temp是位于添加位置的前一个节点，否则插入不了
HeroNode temp = head;
boolean flag = false; //标识添加的编号是否存在，默认为false
while (true){
if(temp.next == null){//说明temp已经在链表的最后了
break; //不管找到没找到 都到最后了
}
if(temp.next.no > heroNode.no){ //位置找到了，就在temp的后面插入就行
break;
}else if(temp.next.no == heroNode.no){ //说明编号已经存在，不能插入
flag = true; //说明编号存在
break;
}
temp = temp.next; //后移，遍历当前列表
}
if(flag){
System.out.println("不能添加，编号已经存在\n" + heroNode.no);
}else {
//插入
heroNode.next = temp.next;
temp.next = heroNode;
}
}
//修改节点的信息，根据编号来修改，并且编号不能修改
//说明
//1 根据newHeroNode的编号来修改即可
public void update(HeroNode newHeroNode){
//判断是否为空
if(head.next == null){
System.out.println("链表为空");
return;
}
//找到要修改的节点，根据no编号
//定义一个辅助变量
HeroNode temp = head.next;
boolean flag = false; //表示是否找到该节点
while(true){
if(temp == null){
break; //已经遍历完链表了
}
if(temp.no == newHeroNode.no){
//找到了
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.name = newHeroNode.name;
temp.nickName = newHeroNode.nickName;
}else {
System.out.println("没找到要修改的节点:" + newHeroNode.no);
}
}
//删除节点 按照编号
//我们在比较时，是temp.next.no和 需要删除的节点no比较
public void delete(int no){
//判断是否为空
if(head.next == null){
System.out.println("链表为空");
return;
}
//找到要删除的节点的前一个节点，根据no编号
//定义一个辅助变量
HeroNode temp = head;
boolean flag = false;
while (true){
if(temp.next == null){
break;
}
if(temp.next.no == no){
flag = true;
break;
}
temp = temp.next; //后移
}
if(flag){
temp.next = temp.next.next;
}else {
System.out.println("没找到指定的no：" + no);
}
}
//显示链表 遍历
public void list(){
//判断链表是否为空
if(head.next == null){
System.out.println("链表为空");
return;
}
//因为头节点不能动 所以我们需要一个辅助变量来遍历
HeroNode temp = head.next;
while (true){
//判断是否到链表的最后
if(temp == null){
break;
}
//输出节点信息
System.out.println(temp.toString());
//将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;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}
单链表面试题
1 求单链表的有效节点个数(如果是带头节点的链表，需要不统计头节点）
/**
* 面试1 求单链表的有效节点个数(如果是带头节点的链表，需要不统计头节点）
* @param head 链表头节点
* @return 有效节点个数
*/
public static int getLength(HeroNode head){
if(head.next == null){
return 0;
}
int length = 0;
//定义一个辅助变量 这里我们没有统计头节点
HeroNode cur = head.next;
while (cur != null){
length++;
cur = cur.next;
}
return length;
}
2 查找单链表的倒数第k个节点
/**
* 面试2 查找单链表的倒数第k个节点
* 思路
* 1 编写一个方法，接收head节点，同时接收一个indx
* 2 index 表示是倒数的index个节点
* 3 先把链表从头到位遍历，得到链表的总长度 ---> getLength
* 4 得到size后，我们从链表的第一个开始遍历，遍历（size-index）个，就可以得到
* 如果找到了则返回该节点，否则返回null
*/
public static HeroNode findLastIndexNode(HeroNode head,int index){
//判断如果链表为空，直接返回空
if(head.next == null){
return null;
}
//第一次遍历 得到链表的长度
int size = getLength(head);
//第二次遍历 size-index 位置，就是我们倒数的第K个节点
//先做一个数据的检验
if(index <= 0 || index > size){
System.out.println("输入数字有误");
return null;
}
//定义一个辅助变量 for 循环定位到倒数的index
HeroNode cur = head.next; //指向第一个节点
for(int i = 0; i < size-index; i++){
cur = cur.next;
}
return cur;
}
3 反转单链表 
/**
* 面试题3 反转单链表
* @param head
* @return
*/
public static HeroNode ReverseList(HeroNode head){
//先判断是不是为空
if(head.next == null || head.next.next == null){
System.out.println("原链表为空/只有一个");
return head;
}
//定义指针，依次从原来的链表中取，
HeroNode cur = head.next; //先让他指向第一个
HeroNode next = null; //指向当前节点【cur】的下一个节点
HeroNode reverseHead = new HeroNode(0,"","");//一个新的临时头节点
//从头遍历原来的列表，每遍历一个节点，就将其取出
while (cur != null){
//注意顺序，先指针下移，然后取，然后插入reverseHead这个新链表的头部
next = cur.next; //先保留cur的下一个节点
//直接头插法
cur.next = reverseHead.next;
reverseHead.next = cur;
//等原链表 遍历到了末尾 就让head.next = reverseHead.next; 返回就行了
if(next == null){
head.next = reverseHead.next;
break;
}else {
cur = next;
}
}
return head;
}
4 从尾到头打印单链表
方法1 反向遍历 方法二 stack栈
/**
* 面试4 逆序打印单链表
* 采用 栈的方式 先进后出
* @param head
*/
public static void ReverseOutPutList(HeroNode head){
//如果单链表只有一个或0个直接输出
if(head.next == null){
return;
}
Stack<HeroNode> stacks = new Stack<>();
//遍历链表
HeroNode cur = head.next;
while (cur != null){
stacks.push(cur);
cur = cur.next;
}
while (stacks.size() > 0){
System.out.println(stacks.pop());
}
}
5 合并两个有序单链表，合并之后的链表仍然有序（我用双向链表实现）
递归实现，非递归实现，双向链表实现
非递归（网上找的）
public static void combineList(Person head1,Person head2){ Person temp1 = head1.next; Person temp2 = head2.next; Person newHead = new Person(0,""); if(head1.next == null){ newHead.next = head2.next; }else if (head2.next == null){ newHead.next = head1.next; } Person temp3 = newHead; while(temp1 != null || temp2 != null){ if(temp1 == null && temp2 != null){ //一个空了 把另一个剩下的全装了 temp3.next = temp2; temp2 = temp2.next; }else if(temp2 == null && temp1 != null){ temp3.next = temp1; temp1 = temp1.next; }else { if (temp1.id <= temp2.id) { temp3.next = temp1; temp1 = temp1.next; } else { temp3.next = temp2; temp2 = temp2.next; } } temp3 = temp3.next; } ———————————————— 原文链接：https://blog.csdn.net/new_buff_007/article/details/98595530双向链表
思路分析
代码实现
注意！！！！有序插入的时候小心最后一个的问题。
package com.cheung.linkedlist;
import java.util.Stack;
public class DoubleLinkedListDemo {
public static void main(String[] args) {
//测试
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
//加入 按照编号
doubleLinkedList.add(new HeroNode2(1,"宋江","及时雨"));
doubleLinkedList.add(new HeroNode2(2,"林冲","豹子头"));
doubleLinkedList.add(new HeroNode2(3,"卢俊义","玉麒麟"));
doubleLinkedList.add(new HeroNode2(4,"唔用","智多星"));
//输出测试
doubleLinkedList.list();
doubleLinkedList.update(new HeroNode2(2,"冲冲子","豹子头"));
doubleLinkedList.delete(3);
System.out.println("修改后的链表情况");
doubleLinkedList.list();
doubleLinkedList.addByOrder(new HeroNode2(3, "卢儿","麒麟"));
doubleLinkedList.addByOrder(new HeroNode2(7, "杨过","羊来"));
System.out.println("修改后的链表情况");
doubleLinkedList.list();
}
}
//定义DoubleLinkedList 管理我们的英雄
class DoubleLinkedList {
//先初始化一个头节点，头节点不要动 不存放具体的数据
private HeroNode2 head = new HeroNode2(0, "", "");
public void setHead(HeroNode2 head) {
this.head = head;
}
public HeroNode2 getHead() {
return head;
}
//添加节点到双向
//思路 当不考虑编号顺序时：1找到当前链表最后节点 2将最后这个节点的next 指向 新的节点
public void add(HeroNode2 heroNode) {
//因为head节点不能动，因此我们需要一个辅助变量遍历temp
HeroNode2 temp = head;
//遍历链表找到最后
while (true) {
// 找到链表的最后
if (temp.next == null) {
break;
}
//如果没找到最后，就将temp后移
temp = temp.next;
}
//当退出while循环时，temp就指向了链表的最后
//将最后的这个节点的next指向新的节点
temp.next = heroNode;
heroNode.pre = temp;//形成双向链表
}
//第二种方式 在添加英雄时，根据排名将英雄插入到指定位置
// （如果有这个排名，则添加失败，并给出提示）
public void addByOrder(HeroNode2 heroNode){
//因为head节点不能动，因此我们需要一个辅助指针遍历temp
HeroNode2 temp = head.next;
boolean flag = false; //标识添加的编号是否存在，默认为false
while (true){
if(temp.no > heroNode.no){ //位置找到了，就在temp的前面插入就行
break;
}else if(temp.no == heroNode.no){ //说明编号已经存在，不能插入
flag = true; //说明编号存在
break;
}
if(temp.next == null){//说明temp已经是链表最后一个节点了
break; //不管找到没找到 都到最后了，那么我们需要插到最后
}
temp = temp.next; //后移，遍历当前列表
}
if(flag){
System.out.println("不能添加，编号已经存在\n" + heroNode.no);
}else {
//这里又有特殊情况了。要是在末尾。。那还得优化
if(temp.next == null && heroNode.no > temp.no){
//插入
heroNode.pre = temp.pre;
temp.next = heroNode;
}else {
//插入
temp.pre.next = heroNode;
heroNode.pre = temp.pre; //前一个绑上了
temp.pre = heroNode;
heroNode.next = temp; //后一个也榜上了
}
}
}
//显示链表 遍历
public void list() {
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//因为头节点不能动 所以我们需要一个辅助变量来遍历
HeroNode2 temp = head.next;
while (true) {
//判断是否到链表的最后
if (temp == null) {
break;
}
//输出节点信息
System.out.println(temp.toString());
//将temp后移
temp = temp.next;
}
}
//修改一个节点的内容，可以看到双向链表的节点的修改和单向链表一样
public void update(HeroNode2 newHeroNode) {
//判断是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//找到要修改的节点，根据no编号
//定义一个辅助变量
HeroNode2 temp = head.next;
boolean flag = false; //表示是否找到该节点
while (true) {
if (temp == null) {
break; //已经遍历完链表了
}
if (temp.no == newHeroNode.no) {
//找到了
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.name = newHeroNode.name;
temp.nickName = newHeroNode.nickName;
} else {
System.out.println("没找到要修改的节点:" + newHeroNode.no);
}
}
//从双向链表 删除节点 按照编号
public void delete(int no) {
//判断是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//找到要删除的节点的前一个节点，根据no编号
//定义一个辅助变量
HeroNode2 temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
break;
}
if (temp.no == no) {
flag = true;
break;
}
temp = temp.next; //后移
}
if (flag) {
temp.pre.next = temp.next;
//这个代码有风险 假如我们删除的是最后一个节点，
if (temp.next != null) {
temp.next.pre = temp.pre;
}
} else {
System.out.println("没找到指定的no：" + no);
}
}
}
//定义HeroNode2，每个HeroNode对象就是一个节点
class HeroNode2 {
public int no;
public String name;
public String nickName;
public HeroNode2 next; //指向下一个节点，默认为null
public HeroNode2 pre; //指向前一个节点，默认为null
public int getNo(){
return this.no;
}
public HeroNode2(int no, String name, String nickName) {
this.no = no;
this.name = name;
this.nickName = nickName;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}
约瑟夫环问题
图没画完，最后3 自己也出了
实现构建和遍历
- 构建
- 遍历
package com.cheung.linkedlist;
public class Josephu {
public static void main(String[] args) {
//测试 构建环形链表和构建是否okk
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(25); //加入五个小孩节点
circleSingleLinkedList.showBoy();
}
}
//创建一个环形的单向链表
class CircleSingleLinkedList{
//创建一个first节点，当前没有编号
private Boy first = null;
//添加小孩节点，构建成一个环形链表
public void addBoy(int nums){
if(nums < 1){ //简单的数据校验
System.out.println("输入的数据不正确");
return;
}
Boy curBoy = null; //辅助遍历，帮助构建环形链表
//使用for循环来创建我们的环形链表
for(int i = 1; i <= nums; i++){
//根据编号创建小孩节点
Boy boy = new Boy(i);
//考虑第一个小孩比较特别
if(i == 1){
first = boy;
first.setNext(first); //构成一个环
curBoy = first; //让辅助指针指向第一个小孩 为啥要用curBoy 因为first不能动
}else {
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy; //让辅助指针指向末尾
}
}
}
//遍历当前环形链表
public void showBoy(){
//判断链表是否为空
if(first == null){
System.out.println("链表为空");
return;
}
//因为first不能动，因此我们还是需要一个辅助指针
Boy curBoy = first;
while (true){
System.out.printf("小孩的编号 %d \t",curBoy.getNo());
if(curBoy.getNext() == first){
System.out.println("遍历完毕!");
break;
}
curBoy = curBoy.getNext(); //让curBoy后移
}
}
}
//创建一个Boy类，表示一个节点
class Boy{
private int no; //编号
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;
}
}
出队编号顺序问题
//根据用户的输入，计算出小孩出圈的顺序
/**
* @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();
}
//小孩报数前，先让first和helper移动k-1次,找到报数起始位置
for(int j = 0; j < startNo - 1; j++){
first = first.getNext();
helper = helper.getNext();
}
//当小孩报数时，让first和helper指针同时移动countNum-1，然后出圈
//这里是一个循环操作，直到圈中只有一个节点
while(true){
if(helper == first){//说明只剩一个节点了
break;
}else {
//让first和helper指针同时移动countNum-1，然后出圈
for(int j = 0; j < countNum - 1; j++){
first = first.getNext();
helper = helper.getNext();
}
//这时，first指向的节点就是要出圈的小孩节点
System.out.printf("小孩:%d出圈\n", first.getNo());
//这时，将first指定的小孩出圈
first = first.getNext();
helper.setNext(first);
}
}
System.out.printf("最后留在圈中的小孩是%d",first.getNo());
}
测试
public static void main(String[] args) {
//测试 构建环形链表和构建是否okk
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5); //加入五个小孩节点
circleSingleLinkedList.showBoy();
//测试小孩出圈是否正确
circleSingleLinkedList.countBoy(1,2,5);
}
数组实现
public class yuesefu
{
public static void main(String[] args)
{
int N=5,S=1,D=2; //N总数、S第一次在哪儿开始数、D数几次
int n=N; //n是剩下的人数
int []a=new int [N]; //用数组存储人的序号
for(int i=0;i<a.length;i++) //数组赋值1、2……
{
a[i]=i+1;
}
int key=(S+D-2)%n;//key是第一次简化后应该被显示出来的数组下标，S+D-1是个数，再减1就是那个数的下标
for(int i=1;i<=N-1;i++) //循环N-1次取出N-1个那么只剩1个了，即剩下被赦免那个
{
System.out.print(a[key]+"\t"); //把要取出的人显示出来
if(key<n-1) //如果取出的数不是最后一个，要把这个数后面的数前移
{
for(int j=key;j<=n-2;j++)//这里用覆盖的方法，比如取出的数是a[2]，那么将a[3]、a[4]……向前覆盖
{ //假如覆盖3次以后，那么数组最后面的3个数是没有实际意义的，就不必向前覆盖，即前移到n-2
a[j]=a[j+1]; //j<=n-2是因为 a[j]=a[j+1];即最后会是a[n-2]=a[n-1];最后一个位置没有意义
}
}
n--;//将人数减少，数组是不变的，但是数组后面无意义的数就不算了，即假装数组在变短，数组只有前面有意义
key=(key+D-1)%n; //这里更新下一个应该被取出的数在数组里的下标
}
System.out.print(a[0]); //输出最后一个数，即被赦免的数，而且a[1]、a[2]……在我们看来没意义了
}
}
若有收获，就点个赞吧
0 人点赞
