承接上文, 在介绍完线性结构的数组和队列后, 开始学习线性结构的链表和栈的相关知识
在我们的生活中, 最符合链表结构(准确的说是双链表)的物体的就是火车了(如下图). 我们在车厢内时,每次只能从本车厢到下一个车厢或者上一个车厢,如同对链表的遍历操作一样~~~
开完火车后, 本司机来和大家一起学习链表吧~~~ 作为数据结构中线性结构的组成部分, 链表(Linked List)是一种非连续,非顺序的存储结构. 它是由一系列节点构成. 每个节点包含 存放数据的数据域 和 存放指针的指针域 构成. 相较于线性结构的顺序表, 它的操作方式更加复杂
单链表: 链式存储结构, 即: 由节点组成, 每个节点通过指针相连. 不同的是单链表只有一个指针, 用于指向后继元素(下一个节点)
物理存储效果图
单链表(含head节点)逻辑结构如下
在这里使用单链表实现水浒英雄榜(排名, 名称, 人送外号)的增删改查操作 这里的链表实际上是起到了和数据库一样的作用 在我们今后的开发中, 如果需要用到数据不允许保存在数据库中(提高效率), 可以考虑使用链表进行实现哦 !
第一种方式 添加英雄时, 直接添加到链表尾部
temp = temp.next;
思路图
package ah.sz.tp.algorithm1;
/**
* 单链表实现水浒英雄榜
* 1. 创建节点模型, 规定排行, 名字, 外号, 下一个节点; 重写构造,toString()
* 2. 创建链表实体, 创建头节点属性, 创建增删改查的方法
* 3. 在main()中进行操作
*
* @author TimePause
* @create 2020-01-09 16:52
*/
public class SingleLinkedListDemo {
public static void main(String[] args) {
Node hero1 = new Node(1, "宋江", "及时雨");
Node hero2 = new Node(2, "卢俊义", "玉麒麟");
Node hero3 = new Node(3, "吴用", "智多星");
Node hero4 = new Node(4, "林冲", "豹子头");
// 将这些节点加入链表中
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.add(hero1);
singleLinkedList.add(hero3);
singleLinkedList.add(hero2);
singleLinkedList.add(hero4);
// 显示链表数据
singleLinkedList.showLinkedList();
}
}
class Node{
public int no;
public String name;
public String nickName;
public Node next;
public Node(int no, String name, String nickName) {//去掉next,因为它需要在我们添加时手动指定
this.no = no;
this.name = name;
this.nickName = nickName;
}
@Override
public String toString() {//需要将next的输出去掉
return "Node{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}
class SingleLinkedList{
// 初始化头节点
private Node head = new Node(0, "", "");
/**
* 添加节点到单链表(不考虑顺序)
* 1. 找到当前链表的最后一个节点
* 2. 将这个节点的next 指向新的节点
*/
public void add(Node heroNode){
//因为head节点不能移动, 因此我们需要辅助变量temp来辅助遍历
Node temp=head;
// 定义循环结束的变量
boolean flag = true;
while (flag){
// 如果当前节点next为null,说明是链表的最后
if (temp.next==null){
// 这个节点的next 指向新的节点
temp.next = heroNode;
flag = false;
}
// 如果执行到这里, 说明没有找到最后
temp = temp.next;
}
}
/**
* 显示整个链表
*/
public void showLinkedList(){
// 判断链表是否为空
if (head.next==null){
System.out.println("当前列表为空,请手动添加数据~~~");
return;
}
// 不为空, 则遍历每个节点, 借助辅助变量temp
Node temp = head.next;
while (true){
// 如果是最后
if (temp==null){
break;
}
//输出节点信息
System.out.println(temp);
// 一定要将temp后移
temp = temp.next;
}
}
}
结果展示 从这里结果看出, 如果我们乱序插入, 那么结果也是乱序的
temp.next.no>heroNode.no
,列如数据1和数据4之间temp就定位到了数据1
首先我们会让插入的节点的next指针指向temp.next域(数据4), 然后将temp.next节点指向需要插入的节点(要插入节点的上一个节点的指针指向要插入的这节点)
heroNode.next = temp.next; //=左边相当于指针(heroNode.next为heroNode的next指针),=右边相当于实际的节点(temp.next为temp的下一个节点) temp.next = heroNode;
思路图
根据思路图, 创建按顺序添加的方法
/**
* 添加英雄时, 根据排名将英雄添加到指定的位置
* 如果排名已存在,则显示已存在
*/
public void addByOrder(Node heroNode) {
//因为头节点不能动, 我们需要使用辅助(相当于c中的指针)变量,来帮助找到添加的位置
//因为是单链表, 因为我们找到temp是位于添加位置前的一个节点, 否则插入不了
Node temp = head;//这里的temp实际上指待插入节点的前一个节点
// 用于标志插入的编号是否存在
boolean flag = false;
while (true) {
if (temp.next == null) {//说明位于最后
break;
}
if (temp.next.no > heroNode.no) {//说明这个就是应该插入的位置
break;
} else if (temp.next.no == heroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
//通过flag判断插入的元素是否存在
if (flag) {//已存在
System.out.printf("您要保存的英雄 %d 已经存在,不能够加入\n", heroNode.no);
} else {//说明不存在,执行插入
//将插入节点的指针指向下一个节点
heroNode.next = temp.next;
//将要插入节点的上一个节点的指针指向要插入的节点
//temp.next在左边: 表示要插入节点的上一个节点的指针, 在右边表示要插入节点的下一个节点!!!
temp.next = heroNode;
}
}
测试该方法
public static void main(String[] args) {
Node hero1 = new Node(1, "宋江", "及时雨");
Node hero2 = new Node(2, "卢俊义", "玉麒麟");
Node hero3 = new Node(3, "吴用", "智多星");
Node hero4 = new Node(4, "林冲", "豹子头");
// 将这些节点加入链表中
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
// 显示链表数据
singleLinkedList.showLinkedList();
}
}
可以看到即使乱序插入也会被纠正
添加用于修改英雄属性的方法
/**
* 修改英雄属性
*/
public void update(Node newHeroNode) {
// 首先需要判断是否为空
if (head.next == null) {
System.out.println("队列为空");
}
// 判断是需要修改的节点否存在
boolean flag = false;
//因为是单链表, 因为我们找到temp是位于添加位置前的一个节点
Node temp = head.next;
while (true) {
if (temp == null) {//我们首先会设想为空值的情况,说明一件到链表末尾
break;//遍历完未找到
}
if (temp.no == newHeroNode.no) {//找到
flag = true;
break;
}
//让temp不停的往下走, 即令temp不断的指向下一个节点
temp = temp.next;
}
if (flag) {
// 修改其姓名和外号,编号不可修改
temp.name = newHeroNode.name;
temp.nickName = newHeroNode.nickName;
} else {
System.out.printf("您修改的编号为 %d 的英雄不存在!!!", newHeroNode.no);
}
}
main方法测试并显示结果
singleLinkedList.update(new Node(4,"chy","时间静止"));
// 显示链表数据
singleLinkedList.showLinkedList();
思路
temp.next.no == delHerono
temp.next.next
. 待删除节点没有被引用后会被GC回收思路图
代码实现
/**
* 根据英雄编号删除节点
*/
public void del(int delHerono) {
// 头节点不能动, 需要辅助变量
Node temp = head;
// 标记要删除的节点是否存在
boolean flag = false;
while (true) {
if (temp.next == null) {//说明已到链表的末尾
break;
}
if (temp.next.no == delHerono) {
flag = true;
break;
}
temp = temp.next;
}
if (flag){
//将当前节点的下个节点指针指向下下个节点,相当于是删除了下一个节点(依靠GC)
temp.next = temp.next.next;
}else {
System.out.println("要删除的节点不存在");
}
}
测试方法效果
singleLinkedList.del(1);
singleLinkedList.del(4);
singleLinkedList.del(2);
singleLinkedList.del(3);
// 显示链表数据
singleLinkedList.showLinkedList();
准备
类对象.成员变量
,如果设置成private,则需要通过get()或set()方法获取相关的属性 class Node {
public int no;
public String name;
public String nickName;
public Node next;
public Node(int no, String name, String nickName) {//去掉next,因为它需要在我们添加时手动指定
this.no = no;
this.name = name;
this.nickName = nickName;
}
@Override
public String toString() {//需要将next的输出去掉
return "Node{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}
class SingleLinkedList {
// 初始化头节点
public Node head = new Node(0, "", "");
// 获取头节点
public Node getHead() {
return head;
}
}
/**
* 面试题1: 获取单链表节点的个数(不统计头节点)
* 但是要通过头节点
*/
public static int getLinkedListLength(Node head) {
if (head.next == null) {//说明当前节点长度为0
return 0;
}
//定义辅助变量
Node temp = head.next;
int length = 0;
while (temp != null) {//判断该变量是否为空
length++;
temp = temp.next;//执行循环
}
return length;
}
结果展示
System.out.println(getLinkedListLength(singleLinkedList.getHead()));
// 显示链表数据
singleLinkedList.showLinkedList();
思路
代码实现
/**
* 面试题2: 查找单链表中倒数第k(index)个节点(1的基础上进行)
* 1. 编写一个方法, 接收head, 接收index表示倒数第k个节点
* 2. 遍历链表, 得到总长度 size=getLinkedListLength()
* 3. 得到size会后. 重新遍历链表, 便利到 (size-index)个
* 4. 如果找到则返回该节点, 找不到则提示空
*/
public static Node findLastIndexOfLinkedList(Node head, int index) {
if (head.next == null) {
return null;
}
//获取总长度
int size = getLinkedListLength(head);
// 对输入的index进行判断
if (index <= 0 || index > size) {
System.out.println("设置的索引有误,请重新设置");
}
//辅助变量, 不包括头节点
Node temp = head.next;
// 重新遍历链表
for (int i = 0; i < size - index; i++) {
temp = temp.next;//第size-index即为倒数第index节点,对应temp.next的那个节点
}
return temp;
}
结果展示
// 显示链表数据
singleLinkedList.showLinkedList();
//倒数第k个节点为
System.out.println("倒数第k个节点为");
Node node = findLastIndexOfLinkedList(singleLinkedList.getHead(), 1);
System.out.println(node);
思路图
思路
head.next = reverseHead.next
, ‘=’:指针的指向功能
即: 原链表头节点窃取了新链表(反转后)的果实, 有点像袁世凯窃取了国民gm的胜利果实 /**
* 面试题3:实现单链表反转
* 1. 定义一个节点,代表反转节点 reverseHead=new HeroNode()
* 2. 从头到尾遍历原来的链表, 每遍历一个节点, 就将其取出, 放在新链表reverseHead的最前面
* 3. 原来的链表 head.next = reverseHead.next '=':指针的指向功能
*/
public static void reverseLinkedList(Node head){
// 如果当前列表为空, 或者只有一个节点, 无需反转, 直接返回
if (head.next==null || head.next.next==null){
return;
}
// 定义一个辅助变量/指针, 遍历原来的链表
Node cur = head.next;
// 定义当前节点[cur]的下一个节点
Node next= null;
// 新链表的头结点
Node reverseHead = new Node(0, "", "");
// 遍历原来的列表, 每遍历一个节点, 就将其取出, 放在新链表reverseHead的第一个节点
// 仔细思考
while (cur!=null){
// 1.保存当前节点的下一个节点
next = cur.next;
// 2.将cur的指针指向新的链表头结点后的第一个节点
cur.next = reverseHead.next;
// 3.将新链表的头结点指针指向cur
reverseHead.next = cur;
// 4.相当于cur后移
cur = next;
}
// 将原来头结点指针指向新链表头结点后第一个节点
head.next = reverseHead.next;
}
结果展示
// 显示链表数据
singleLinkedList.showLinkedList();
System.out.println("实现链表的反转");
reverseLinkedList(singleLinkedList.getHead());
// 显示链表数据
singleLinkedList.showLinkedList();
思路图
思路
栈的简单使用
/**
* 测试栈的使用
*
* @author TimePause
* @create 2020-01-10 16:38
*/
public class TestStack {
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
//入栈
stack.add("man1");
stack.add("man2");
stack.add("man3");
//出栈
while (stack.size()>0){
System.out.println(stack.pop());
}
}
}
代码实现
/**
* 面试题4: 实现单链表的逆序打印
* 利用栈(先进后出), 将各个节点压入栈中, 然后再弹出打印
*/
public static void reversePrint(Node head){
// 判断链表是否为空
if (head.next==null){
return;
}
// 创建一个辅助变量/指针
Node cur = head.next;
// 创建一个栈
Stack<Node> nodeStack = new Stack<>();
while (cur!=null){
nodeStack.add(cur);
cur = cur.next;
}
while (nodeStack.size()>0){
System.out.println(nodeStack.pop());
}
}
结果展示
// 显示链表数据
singleLinkedList.showLinkedList();
System.out.println("逆序打印链表. 通过栈的方式");
reversePrint(singleLinkedList.getHead());
我们可以查看一下双向链表的定义 双向链表也叫双链表,是链表的一种,有节点组成. 它的每个数据节点中都有两个指针,分别指向直接后继和直接前驱。 从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
为了解决单链表的不足引入了双链表, 下面来简单比较一下单链表和双链表
通过下面图解来理解
根据上面逻辑图, 使用双链表实现基本增删改查, 代码如下
package ah.sz.tp.algorithm1;
/**
* 使用双链表完成水浒英雄排行榜
*
* @author TimePause
* @create 2020-01-10 20:37
*/
public class DoubleLinkedListDemo {
public static void main(String[] args) {
// 创建并添加四条数据
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
// 创建双链表
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.add(hero1);
doubleLinkedList.add(hero2);
doubleLinkedList.add(hero3);
doubleLinkedList.add(hero4);
// 执行修改操作
//doubleLinkedList.undate(new HeroNode(4,"chy","时间静止不是简史"));
//执行删除操作
doubleLinkedList.delete(4);
doubleLinkedList.showDoubleLinkedList();
// 显示数据
}
}
class DoubleLinkedList{
//双链表的头节点
public HeroNode head = new HeroNode(0, "", "");
/**
* 双向链表的删除(无序)
* 核心代码
* temp.pre.next=temp.next
* temp.next.pre=temp.pre
* 解析
* temp的pre(上一个)节点的next指针指向temp的下一个节点=>相当于上面逻辑图中的那条红线,绕过了temp=>建立了next关系
* temp的next(下一个节点)的next指针指向temp的上一个节点=>相当于上面的逻辑图中的红线下面的蓝色线,也是绕过了temp=>建立了pre关系
* 但是,在执行temp.next.pre=temp.pre需要注意
* 如果需要被删除的元素temp位于末尾,则temp.next.pre=null,会报空指针异常
*/
public void delete(int no){
//判断该双链表是否为空
if (head.next==null){
System.out.println("该链表长度为空");
}
// 创建辅助指针/变量, 是head的下一个节点, 单链表中这里是head节点
// 是因为单链表删除时, 需要找到被删除节点的上一个节点,然后令其指向被删除节点下一个节点, 而双链表可以自动删除
HeroNode 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的下一个节点=>相当于上面逻辑图中的那条红线,绕过了temp=>建立了next关系
temp.pre.next=temp.next;
//temp的next(下一个节点)的next指针指向temp的上一个节点=>相当于上面的逻辑图中的红线下面的蓝色线,也是绕过了temp=>建立了pre关系
// 如果需要被删除的元素temp位于末尾,则temp.next.pre=null,会报空指针异常,需要判空
if (temp.next!=null){
temp.next.pre = temp.pre;
}
}else {
System.out.printf("要删除排行%d的英雄不存在",no);
}
}
/**
* 双向链表的修改,根据no(和单向链表一样,知识节点类型发生了变化)
*/
public void undate(HeroNode updateHeroNode){
//判断第一个节点是否为空
if (head.next==null){
System.out.println("该链表长度为空");
return;
}
//定义辅助指针/变量
HeroNode temp = head.next;
//定义该节点是否找到
boolean flag = false;
while (true){
if (temp==null){
break;
}
if (temp.no==updateHeroNode.no){//编号相等说明找到
flag=true;
break;
}
//不断移动指针
temp = temp.next;
}
// 根据是否找到节点执行相关逻辑
if (flag){
temp.name = updateHeroNode.name;
temp.nickName = updateHeroNode.nickName;
}else {
System.out.printf("没有找到排行%d的英雄,不能修改",updateHeroNode.no);
}
}
/**
* 双向链表的添加
* 相较于单向链表多了两行代码
* temp.next=newHeroNode
* newHeroNode.pre=temp
*/
public void add(HeroNode newHeroNode){
//需要辅助变量, 而且因为是添加(可能会从第一个开始添加),辅助变量首先要位于head,而不是head.next
//如果head.next位于=左边, 说明head的next指针, 如果位于=右边这说明是head的后面一个元素
HeroNode temp = head;
while (temp.next!=null){
temp = temp.next;
}
// 如果为空,说明到达双链表尾部
// 在两个节点之间建立双链表关系
temp.next = newHeroNode;
newHeroNode.pre = temp;
}
/**
* 双向链表的遍历
*/
public void showDoubleLinkedList(){
// 判断链表的第一个节点是否为空
if (head.next==null){
System.out.println("链表为空");
return;
}
//定义辅助指针/变量
HeroNode temp = head.next;
while (temp!=null){
System.out.println(temp.toString());
temp = temp.next;
}
}
}
class HeroNode{
public int no;
public String name;
public String nickName;
public HeroNode pre; //前一个节点
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 + '\'' +
'}';
}
}
结果展示
// 创建并添加四条数据
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
// 创建双链表
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.add(hero1);
doubleLinkedList.add(hero2);
doubleLinkedList.add(hero3);
doubleLinkedList.add(hero4);
doubleLinkedList.showDoubleLinkedList();
双链表,实现有顺序的插入
逻辑图(手残见谅)
思路:判断是否遍历到链表尾部/插入点位置/插入点=>根据不同结果执行相关操作=>指针后移
如果在链表中间找到插入点(temp则位于插入点前,temp.next位于插入点后),确定了位置后则需要
/**
* 双链表的添加(画图,结合图去理解!!!)
*/
public void addByOrder(HeroNode newHeroNode) {
// 添加不需要判空
// 创建一个辅助变量/指针
HeroNode temp = head;
// 创建一个布尔变量,表示待插入是否存在
while (true) {
if (temp.next == null) {//到达链表最后
//如果插入元素在链表最后, 只需要将temp的next指向新节点,新节点的pre指向temp
temp.next = newHeroNode;
newHeroNode.pre = temp;
break;
}
if (temp.next.no > newHeroNode.no) {//找到插入点的位置
/**
* 如果在链表中间找到插入点(temp则位于插入点前,temp.next位于插入点后)
* 1.需要创建一个变量nextnode存放插入点的下一个节点temp.next
* 2.插入点的pre指向temp, temp的next指向插入点
* 3.nextnode的pre指向插入点, 插入点的下一个节点指向nextnode
*/
HeroNode nextnode = temp.next;
newHeroNode.pre = temp;
temp.next = newHeroNode;
newHeroNode.next = nextnode;
nextnode.pre = newHeroNode;
break;
}
if (temp.next.no == newHeroNode.no) {//找到插入点
System.out.println("要插入的节点已经存在");
break;
}
//指针后移
temp = temp.next;
}
}
结果展示
doubleLinkedList.addByOrder(hero1);
doubleLinkedList.addByOrder(hero4);
doubleLinkedList.addByOrder(hero2);
doubleLinkedList.addByOrder(hero3);
// 显示数据
doubleLinkedList.showDoubleLinkedList();
Josephu 问题为:设编号为1,2,… n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m 的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。
提示 用一个不带头结点的循环链表来处理Josephu 问题:先构成一个有n个结点的单循环链表,然后由k结点起从1开始计数,计到m时,对应结点从链表中删除,然后再从被删除结点的下一个结点又从1开始计数,直到最后一个结点从链表中删除算法结束。
示意图说明—假设含有五个节点的单循环链表执行约瑟夫问题的图解
单循环链表构建和遍历的思路图
实现代码
package ah.sz.tp.algorithm1;
/**
* 单向循环链表学习
*
* @author TimePause
* @create 2020-01-11 20:30
*/
public class SingleCircleLinkedListDemo {
public static void main(String[] args) {
// SingleCircleLinkedList singleCircleLinkedList = new SingleCircleLinkedList();
SingleCircleLinkedListDemo demo = new SingleCircleLinkedListDemo();
SingleCircleLinkedList list = demo.new SingleCircleLinkedList();
list.add(5);
list.showSingleCircleLinkedList();
}
/**
* 创建单向循环链表类
*/
class SingleCircleLinkedList{
// 创建第一个节点
private Boy first=null;
// 创建临时指针/变量
private Boy curBoy=null;
/**
* 添加方法
* @param num 添加几个节点
*/
public void add(int num){
// 对参数进行校验
if (num<1){
System.out.println("添加节点个数有误,请重新添加~~~");
return;
}
//使用for循环来创建我们的环形链表
for (int i=1;i<=num;i++){
//创建下一个节点/子节点
Boy boy=new Boy(i);
// 如果添加一个节点
if (i==1){
//1.将第一个节点boy作为first(相当于其他链表中的头节点)
first=boy;
//2.将boy下一个节点指向first(形成环)
boy.next = first;//也可以写成 boy.setNext(first); 同理,下面都可以
//3. 将指针移动到first(头节点)
curBoy = first;
}else {
// 如果添加1个以上节点
//1. 将辅助变量指向下一个节点boy 2.将boy指向第一个节点(形成环) 3.一阵移动到一下个节点
curBoy.next = boy;
boy.next = first;
curBoy = boy;
}
}
}
/**
* 遍历当前的单向循环链表
*/
public void showSingleCircleLinkedList(){
// 判断链表是否非空
if (first==null){
System.out.println("当前循环链表为空, 无法遍历哦~~~");
return;
}
// 调用辅助指针完成遍历
curBoy = first;
while (true){
System.out.printf("孩子节点的编号%d \n",curBoy.no);
if (curBoy.next==first){
break;
}
curBoy = curBoy.next;
}
}
}
/**
* 创建Boy类,用于存放节点信息
*/
class Boy{
private int no;//编号
private Boy next;//代表指向下一个节点
//带参构造
public Boy(int no){
this.no=no;
}
public int getNo() {
return no;
}
public Boy getNext() {
return next;
}
public void setNo(int no) {
this.no = no;
}
public void setNext(Boy next) {
this.next = next;
}
}
}
思路图
实现代码
/**
* 根据用户输入, 计算小孩出圈的顺序
*
* @param startNo 表示从第几个小孩开始数数
* @param countNum 表示数几下
* @param nums 表示圈中最初有多少个小孩
*/
public void countBoy(int startNo, int countNum, int nums) {
// 1.对参数进行校验
if (startNo < 1 || countNum > nums || startNo > nums) {
System.out.println("参数设置有误,请重新设置!!!");
}
//创建辅助指针, 帮助小孩节点出圈(循环链表)
Boy helper = first;
//2. 让辅助变量helper首先指向这个圈的最后一个节点
while (true) {
if (helper.getNext() == first) {
break;
}
// 指针后移
helper = helper.getNext(); //or helper.next
}
//3. 小孩报数前,先让first和helper移动k-1(startNo-1)次=>从指定地方报数
for (int i = 0; i < startNo - 1; i++) {
//同时移动first和helper指针
first = first.getNext();
helper = helper.getNext();
}
//4.小孩报数时, 让first和helper的指针同时移动m-1(countMun-1),然后出圈
while (true) {
if (helper == first) {//说明圈中只剩下一个元素
break;
}
// 让first和helper的指针同时移动m-1(countMun-1)
for (int j = 0; j < countNum - 1; j++) {
first = first.getNext();
helper = helper.getNext();
}
//这时first要指向的节点, 就是小孩要出圈的节点
System.out.printf("小孩节点%d 要出圈\n", first.getNo());
//5. 将first指向的小孩节点出圈
//思路:结合图知,首先将first移动到要出圈的节点的下一个节点后,让辅助指针去指向下一个节点,这样要出圈的节点就会被GC
first = first.getNext();
helper.setNext(first);
}
System.out.printf("最后留在圈中的小孩的编号为%d \n", first.no);
}
结果展示 创建五个节点的单循环链表, 然后从第1个开始计数, 每到第2人出圈, 总人数为5
SingleCircleLinkedListDemo demo = new SingleCircleLinkedListDemo();
// 创建了内部类, 所以使用这种方式创建内部类对象
SingleCircleLinkedList list = demo.new SingleCircleLinkedList();
// 调用添加方法
list.add(5);
// 调用遍历显示方法
list.countBoy(1, 2, 5);
单身汪的凝视~~~