链表是有序的表的按时它在内存中是存储如下 (内存中的实际结构)
①链表是以结点的方式来存储 是链式存储
②每个节点包含data域、next域指向下一个结点
③如图 发现链表的各个结点不一定是连续存储
④链表分为带头结点的链表 和 不带头结点的链表 根据实际需求来确定
单链表
单链表(带头结点) 逻辑结构 示意图如下
头结点:
①不存放具体数据
②作用就是表示单链表头
添加(创建):
①先创建一个head头结点 作用就是表示单链表的投
②后面我们每添加一个结点 就直接加入到链表的最后
代码1:按照声明的添加的顺序 进行添加
public class danlianbiao {public static void main(String[] args) {HeroNode n1 = new HeroNode(1,"zhangke","zk");HeroNode n2 = new HeroNode(2,"tianjiawen","tjw");HeroNode n3 = new HeroNode(3,"zhangzhiming","zzm");SingleLinkedList singleLinkedList = new SingleLinkedList();singleLinkedList.add(n1);singleLinkedList.add(n2);singleLinkedList.add(n3);singleLinkedList.show();}}//定义此类管理HeroNodeclass SingleLinkedList{//初始化一个头结点 头结点一般不要动private HeroNode head = new HeroNode(0,"","");//添加结点到单项链表public void add(HeroNode heroNode){//当不考虑编号的顺序时//①找到当前链表的最后 结点 ②将最后这个结点的next指向新的结点//因为head结点不能动 所以需要辅助遍历结点tempHeroNode temp = head;//遍历链表 找到最后while(true){if(temp.next==null){break;}temp=temp.next;}//当退出循环时 temp指向了最后temp.next=heroNode;}//显示链表[遍历]public void show(){//先判断链表是否为空if(head.next==null){System.out.println("空");return;}HeroNode temp = head.next;while (true){//判断是否到最后if(temp==null){break;}//输出结点的信息System.out.println(temp);//将temp后移 不然就是死循环temp=temp.next;}}}//定义HeroNode 每个HeroNode对象就是一个结点class HeroNode{public int no;public String name;public String nikeName;public HeroNode next;//指向下一个结点public HeroNode(int no, String name, String nikeName) {this.no = no;this.name = name;this.nikeName = nikeName;}@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +", nikeName='" + nikeName + '\''+'}';}}
代码2:按照编号的顺序 进行添加
tips:①先找到新添加结点的位置 通过赋值变量找到
②新的结点.next = temp.next
③将temp.next=新的结点
public class danlianbiao {public static void main(String[] args) {HeroNode n1 = new HeroNode(1,"zhangke","zk");HeroNode n2 = new HeroNode(2,"tianjiawen","tjw");HeroNode n3 = new HeroNode(3,"zhangzhiming","zzm");SingleLinkedList singleLinkedList = new SingleLinkedList();singleLinkedList.addByNo(n1);singleLinkedList.addByNo(n3);singleLinkedList.addByNo(n2);singleLinkedList.addByNo(n2);singleLinkedList.show();}}//定义此类管理HeroNodeclass SingleLinkedList{//初始化一个头结点 头结点一般不要动private HeroNode head = new HeroNode(0,"","");//添加结点到单项链表public void add(HeroNode heroNode){//当不考虑编号的顺序时//①找到当前链表的最后 结点 ②将最后这个结点的next指向新的结点//因为head结点不能动 所以需要辅助遍历结点tempHeroNode temp = head;//遍历链表 找到最后while(true){if(temp.next==null){break;}temp=temp.next;}//当退出循环时 temp指向了最后temp.next=heroNode;}//按照no添加//如果已经有这个no的结点了 则添加失败 并给出提示public void addByNo(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){break;}else if(temp.next.no==heroNode.no){flag=true;break;}temp=temp.next;}if(flag){System.out.println("已经存在");}else{heroNode.next=temp.next;temp.next=heroNode;}}//显示链表[遍历]public void show(){//先判断链表是否为空if(head.next==null){System.out.println("空");return;}HeroNode temp = head.next;while (true){//判断是否到最后if(temp==null){break;}//输出结点的信息System.out.println(temp);//将temp后移 不然就是死循环temp=temp.next;}}}//定义HeroNode 每个HeroNode对象就是一个结点class HeroNode{public int no;public String name;public String nikeName;public HeroNode next;//指向下一个结点public HeroNode(int no, String name, String nikeName) {this.no = no;this.name = name;this.nikeName = nikeName;}@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +", nikeName='" + nikeName + '\''+'}';}}
代码3:单链表结点的修改
//修改结点的信息public void update(HeroNode heroNode){if(head.next==null){System.out.println("空");return;}HeroNode temp = head.next;boolean flag = false;while (true){if(temp==null){break;//已经遍历结束}if(temp.no==heroNode.no){flag=true;break;}temp=temp.next;}if(flag){temp.name=heroNode.name;temp.nikeName= heroNode.nikeName;}else {System.out.println("没有找到 不能修改");}}
代码4:单链表结点的删除
①先找到需要删除的结点的上一个结点
②temp.next = temp.next.next
③被删除的结点 将不会有其他引用指向 会被垃圾回收机制回收
//删除结点public void delete(int no){HeroNode temp = head;boolean flag = false;while(true){if(temp==null){break;}if(temp.next.no==no){flag=true;break;}temp = temp.next;}if(flag){temp.next = temp.next.next;}else{System.out.println("没找到待删除的结点");}}
综合代码:
public class danlianbiao {public static void main(String[] args) {HeroNode n1 = new HeroNode(1,"zhangke","zk");HeroNode n2 = new HeroNode(2,"tianjiawen","tjw");HeroNode n3 = new HeroNode(3,"zhangzhiming","zzm");HeroNode n4 = new HeroNode(2,"tian","t");SingleLinkedList singleLinkedList = new SingleLinkedList();singleLinkedList.addByNo(n1);singleLinkedList.addByNo(n3);singleLinkedList.addByNo(n2);singleLinkedList.update(n4);singleLinkedList.delete(1);singleLinkedList.show();}}//定义此类管理HeroNodeclass SingleLinkedList{//初始化一个头结点 头结点一般不要动private HeroNode head = new HeroNode(0,"","");//添加结点到单项链表public void add(HeroNode heroNode){//当不考虑编号的顺序时//①找到当前链表的最后 结点 ②将最后这个结点的next指向新的结点//因为head结点不能动 所以需要辅助遍历结点tempHeroNode temp = head;//遍历链表 找到最后while(true){if(temp.next==null){break;}temp=temp.next;}//当退出循环时 temp指向了最后temp.next=heroNode;}//修改结点的信息public void update(HeroNode heroNode){if(head.next==null){System.out.println("空");return;}HeroNode temp = head.next;boolean flag = false;while (true){if(temp==null){break;//已经遍历结束}if(temp.no==heroNode.no){flag=true;break;}temp=temp.next;}if(flag){temp.name=heroNode.name;temp.nikeName= heroNode.nikeName;}else {System.out.println("没有找到 不能修改");}}//删除结点public void delete(int no){HeroNode temp = head;boolean flag = false;while(true){if(temp==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 addByNo(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){break;}else if(temp.next.no==heroNode.no){flag=true;break;}temp=temp.next;}if(flag){System.out.println("已经存在");}else{heroNode.next=temp.next;temp.next=heroNode;}}//显示链表[遍历]public void show(){//先判断链表是否为空if(head.next==null){System.out.println("空");return;}HeroNode temp = head.next;while (true){//判断是否到最后if(temp==null){break;}//输出结点的信息System.out.println(temp);//将temp后移 不然就是死循环temp=temp.next;}}}//定义HeroNode 每个HeroNode对象就是一个结点class HeroNode{public int no;public String name;public String nikeName;public HeroNode next;//指向下一个结点public HeroNode(int no, String name, String nikeName) {this.no = no;this.name = name;this.nikeName = nikeName;}@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +", nikeName='" + nikeName + '\''+'}';}} 面试题:①求单链表中有效结点的个数
②查找单链表中的倒数第k个结点 (新浪面试题)
③单链表的翻转 (腾讯面试题)
④从尾到头打印单链表 (百度面试题 要求方式1:反向遍历 方式2:Stack栈)
⑤合并两个有序的单链表 合并后的链表依然有序
①:
//获取单链表结点的个数(若带头结点 需不统计头结点)public static int getLength(HeroNode heroNode){if(heroNode.next==null){return 0;}int len = 0;HeroNode curr = heroNode.next;//没有统计头结点while(curr!=null){len++;curr=curr.next;}return len;} ②:
//查找单链表中的倒数第k个结点 (新浪面试题)//调用getLen()得到链表的长度 index表示倒数第几个结点//从第一个开始遍历(len-index) 就能得到public static HeroNode findLastNode(HeroNode head,int index){if(head.next==null){return null;}int len = getLength(head);if(index<=0||index>len){return null;}HeroNode curr = head.next;for (int i = 0; i < len-index; i++) {curr=curr.next;}return curr;} ③:
//翻转链表//先定义一个新节点res = new HeroNode()//从头到尾遍历原来的链表 每遍历一个结点 就将其取出 并放在新的链表的最前端//原来的链表head.next = res.next;public static void reverse(HeroNode head){if(head.next==null||head.next.next==null){return;}HeroNode next = null;//指向当前结点[curr]的下一个结点HeroNode curr = head.next;//辅助结点 帮助遍历原来的链表HeroNode newReverse = new HeroNode(0,"","");//遍历原来的链表 每遍历一个结点 就将其取出 并放在新的链表newReverse的最前端while(curr!=null){next=curr.next;//先暂时保存 当前结点的下一个结点curr.next = newReverse.next;//将curr的下一个结点指向新的链表的最前端newReverse.next=curr;//将curr链接到新的链表上curr=next;}head.next=newReverse.next;} ④:
//从尾到头 打印单链表 即:逆序打印//方式1： 先翻转 再遍历（大材小用会破坏原来单链表的结构 不建议这么做）//方式2: 利用栈 将各个结点压入栈中 利用栈 先进后厨的特点 就实现了逆序的打印效果public static void printReverse(HeroNode head){if(head.next==null){return;}//先创建一个栈 将结点压入栈中Stack stack = new Stack<>();HeroNode curr = head.next;//先将当前的结点保存下来while(curr!=null){stack.push(curr);curr=curr.next;}//利用pop打印while (stack.size()>0){System.out.println(stack.pop());}} ⑤: 有头结点的话 要跳过头结点
//合并两个有序链表 要求合并后 仍然有序public static HeroNode hebing(HeroNode h1,HeroNode h2){if(h1==null){return h2;}if(h2==null){return h1;}HeroNode ans = new HeroNode(0,"","");HeroNode t = ans;h1=h1.next;h2=h2.next;while(h1!=null&&h2!=null){if(h1.no 综合代码:
import java.awt.*;import java.util.Stack;public class danlianbiao {public static void main(String[] args) {HeroNode n1 = new HeroNode(1,"zhangke","zk");HeroNode n2 = new HeroNode(2,"tianjiawen","tjw");HeroNode n3 = new HeroNode(3,"zhangzhiming","zzm");HeroNode n4 = new HeroNode(4,"tianjiawen4","tjw");HeroNode n5 = new HeroNode(5,"zhangzhiming5","zzm");SingleLinkedList singleLinkedList = new SingleLinkedList();SingleLinkedList singleLinkedList1 = new SingleLinkedList();singleLinkedList.addByNo(n1);singleLinkedList.addByNo(n2);singleLinkedList.addByNo(n5);singleLinkedList1.addByNo(n3);singleLinkedList1.addByNo(n4);singleLinkedList.show();System.out.println("***************************************");System.out.println(getLength(singleLinkedList.getHead()));System.out.println("***************************************");HeroNode res = findLastNode(singleLinkedList.getHead(),1);System.out.println(res);System.out.println("***************************************");//reverse(singleLinkedList.getHead());//singleLinkedList.show();//System.out.println("***************************************");printReverse(singleLinkedList.getHead());System.out.println("***************************************");HeroNode hebing = hebing(singleLinkedList.getHead(), singleLinkedList1.getHead());SingleLinkedList new1 = new SingleLinkedList();new1.add(hebing);new1.show();}//获取单链表结点的个数(若带头结点 需不统计头结点)public static int getLength(HeroNode heroNode){if(heroNode.next==null){return 0;}int len = 0;HeroNode curr = heroNode.next;while(curr!=null){len++;curr=curr.next;}return len;}//查找单链表中的倒数第k个结点 (新浪面试题)//调用getLen()得到链表的长度 index表示倒数第几个结点//从第一个开始遍历(len-index) 就能得到public static HeroNode findLastNode(HeroNode head,int index){if(head.next==null){return null;}int len = getLength(head);if(index<=0||index>len){return null;}HeroNode curr = head.next;for (int i = 0; i < len-index; i++) {curr=curr.next;}return curr;}//翻转链表//先定义一个新节点res = new HeroNode()//从头到尾遍历原来的链表 每遍历一个结点 就将其取出 并放在新的链表的最前端//原来的链表head.next = res.next;public static void reverse(HeroNode head){if(head.next==null||head.next.next==null){return;}HeroNode next = null;//指向当前结点[curr]的下一个结点HeroNode curr = head.next;//辅助结点 帮助遍历原来的链表HeroNode newReverse = new HeroNode(0,"","");//遍历原来的链表 每遍历一个结点 就将其取出 并放在新的链表newReverse的最前端while(curr!=null){next=curr.next;//先暂时保存 当前结点的下一个结点curr.next = newReverse.next;//将curr的下一个结点指向新的链表的最前端newReverse.next=curr;//将curr链接到新的链表上curr=next;}head.next=newReverse.next;}//从尾到头 打印单链表 即:逆序打印//方式1： 先翻转 再遍历（大材小用会破坏原来单链表的结构 不建议这么做）//方式2: 利用栈 将各个结点压入栈中 利用栈 先进后厨的特点 就实现了逆序的打印效果public static void printReverse(HeroNode head){if(head.next==null){return;}//先创建一个栈 将结点压入栈中Stack stack = new Stack<>();HeroNode curr = head.next;//先将当前的结点保存下来while(curr!=null){stack.push(curr);curr=curr.next;}//利用pop打印while (stack.size()>0){System.out.println(stack.pop());}}//合并两个有序链表 要求合并后 仍然有序public static HeroNode hebing(HeroNode h1,HeroNode h2){if(h1==null){return h2;}if(h2==null){return h1;}HeroNode ans = new HeroNode(0,"","");HeroNode t = ans;h1=h1.next;h2=h2.next;while(h1!=null&&h2!=null){if(h1.noheroNode.no){break;}else if(temp.next.no==heroNode.no){flag=true;break;}temp=temp.next;}if(flag){System.out.println("已经存在");}else{heroNode.next=temp.next;temp.next=heroNode;}}//显示链表[遍历]public void show(){//先判断链表是否为空if(head.next==null){System.out.println("空");return;}HeroNode temp = head.next;while (true){//判断是否到最后if(temp==null){break;}//输出结点的信息System.out.println(temp);//将temp后移 不然就是死循环temp=temp.next;}}}//定义HeroNode 每个HeroNode对象就是一个结点class HeroNode{public int no;public String name;public String nikeName;public HeroNode next;//指向下一个结点public HeroNode(int no, String name, String nikeName) {this.no = no;this.name = name;this.nikeName = nikeName;}@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +", nikeName='" + nikeName + '\''+'}';}}
双向链表为什么用双向链表:
①单向链表,查找的方向只能是一个方向 而双向链表可以向前或者向后查找
②单向链表不能自我删除 需要靠辅助结点 而双向链表可以自我删除,所以之前单向
链表删除结点时 总找到temp temp是待删除结点的前一个结点
③双向链表遍历方法和单链表一样 只是可以向前也可以向后查找
④添加(默认添加到双向链表的最后)
1.先找到双向链表的最后这个结点
2.temp.next = newNode
3.newNode.pre = temp
⑤修改的思路和原来的单向链表一样
⑥删除
1.因为是双向链表 所以可以实现自我删除某个结点
2.直接找到要删除的结点 比如temp
3.temp.pre.next = temp.next
4.temp.next.pre = temp.pre
代码1:双向链表删除结点
//删除结点public void delete(int no){if (head.next==null){System.out.println("空");return;}HeroNode2 temp = head.next;//辅助指针//因为现在直接找到结点就可以删掉 不需要找上一个结点 所以.nextboolean 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("没找到待删除的结点");}}代码2:修改结点的信息
//修改结点的信息public void update(HeroNode2 heroNode){if(head.next==null){System.out.println("空");return;}HeroNode2 temp = head.next;boolean flag = false;while (true){if(temp==null){break;//已经遍历结束}if(temp.no==heroNode.no){flag=true;break;}temp=temp.next;}if(flag){temp.name=heroNode.name;temp.nikeName= heroNode.nikeName;}else {System.out.println("没有找到 不能修改");}} 代码3:添加结点到链表 添加到最后
//添加结点到链表 添加到最后public void add(HeroNode2 heroNode){//当不考虑编号的顺序时//①找到当前链表的最后 结点 ②将最后这个结点的next指向新的结点//因为head结点不能动 所以需要辅助遍历结点tempHeroNode2 temp = head;//遍历链表 找到最后while(true){if(temp.next==null){break;}temp=temp.next;}//当退出循环时 temp指向了最后temp.next=heroNode;heroNode.pre = temp;} 代码4:按照no顺序添加
//按照no添加//如果已经有这个no的结点了 则添加失败 并给出提示public void addByNo(HeroNode2 heroNode){//因为head结点不能动 所以需要辅助遍历结点temp来找到添加的位置//我们找的temp是位于添加位置的前一个结点 否则插入不了HeroNode2 temp = head;boolean flag = false;//表示添加的编号是否存在 默认false//遍历链表 找到最后while(true){if(temp.next==null){//说明temp已经在链表的最后break;}if(temp.next.no>heroNode.no){break;}else if(temp.next.no==heroNode.no){flag=true;break;}temp=temp.next;}if(flag){System.out.println("已经存在");}else{heroNode.next=temp.next;temp.next=heroNode;heroNode.pre=temp;}} 综合代码:
public class shuangxianglianbiao {public static void main(String[] args) {HeroNode2 n1 = new HeroNode2(1,"zhangke","zk");HeroNode2 n2 = new HeroNode2(2,"tianjiawen","tjw");HeroNode2 n3 = new HeroNode2(3,"zhangzhiming","zzm");sxlb s1 = new sxlb();s1.addByNo(n1);s1.addByNo(n3);s1.addByNo(n2);s1.show();HeroNode2 n = new HeroNode2(2,"jiawenbaby","jwbb");s1.update(n);System.out.println();s1.show();s1.delete(3);System.out.println();s1.show();}}class sxlb{//先初始化一个头结点 头结点不要动 不要存放具体的数据privateHeroNode2 head = new HeroNode2(0,"","");//返回头结点public HeroNode2 getHead() {return head;}//按照no添加//如果已经有这个no的结点了 则添加失败 并给出提示public void addByNo(HeroNode2 heroNode){//因为head结点不能动 所以需要辅助遍历结点temp来找到添加的位置//我们找的temp是位于添加位置的前一个结点 否则插入不了HeroNode2 temp = head;boolean flag = false;//表示添加的编号是否存在 默认false//遍历链表 找到最后while(true){if(temp.next==null){//说明temp已经在链表的最后break;}if(temp.next.no>heroNode.no){break;}else if(temp.next.no==heroNode.no){flag=true;break;}temp=temp.next;}if(flag){System.out.println("已经存在");}else{heroNode.next=temp.next;temp.next=heroNode;heroNode.pre=temp;}}//删除结点public void delete(int no){if (head.next==null){System.out.println("空");return;}HeroNode2 temp = head.next;//辅助指针//因为现在直接找到结点就可以删掉 不需要找上一个结点 所以.nextboolean 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("没找到待删除的结点");}}//修改结点的信息public void update(HeroNode2 heroNode){if(head.next==null){System.out.println("空");return;}HeroNode2 temp = head.next;boolean flag = false;while (true){if(temp==null){break;//已经遍历结束}if(temp.no==heroNode.no){flag=true;break;}temp=temp.next;}if(flag){temp.name=heroNode.name;temp.nikeName= heroNode.nikeName;}else {System.out.println("没有找到 不能修改");}}//添加结点到链表 添加到最后public void add(HeroNode2 heroNode){//当不考虑编号的顺序时//①找到当前链表的最后 结点 ②将最后这个结点的next指向新的结点//因为head结点不能动 所以需要辅助遍历结点tempHeroNode2 temp = head;//遍历链表 找到最后while(true){if(temp.next==null){break;}temp=temp.next;}//当退出循环时 temp指向了最后temp.next=heroNode;heroNode.pre = temp;}//显示链表[遍历]public void show(){//先判断链表是否为空if(head.next==null){System.out.println("空");return;}HeroNode2 temp = head.next;while (true){//判断是否到最后if(temp==null){break;}//输出结点的信息System.out.println(temp);//将temp后移 不然就是死循环temp=temp.next;}}}//定义HeroNode 每个HeroNode对象就是一个结点class HeroNode2{public int no;public String name;public String nikeName;public HeroNode2 next;//指向下一个结点 默认为nullpublic HeroNode2 pre;//指向前一个结点 默认为nullpublic HeroNode2(int no, String name, String nikeName) {this.no = no;this.name = name;this.nikeName = nikeName;}@Overridepublic String toString() {return "HeroNode2{" +"no=" + no +", name='" + name + '\'' +", nikeName='" + nikeName + '\''+'}';}} 环形链表

约瑟夫环【单链表、双向链表、约瑟夫环 Java数据结构和算法---链表】示意图:

构建单向环形链表的思路:
1.先创建第一个结点 让first指向该结点 并形成环形
2.后面当我们每创建一个新的结点 就把该结点加入到已有的环形链表中即可
遍历环形链表
1.先让一个辅助指针curr 指向first结点
2.然后通过一个while循环遍历该环形链表即可 curr.next=first 结束
出圈的顺序
比如: 5个人(n=5) 从第一个开始报数(k=1) 每数到2出去(m=2)
1.需要创建一个辅助的阵阵helper 实现应该指向环形链表的最后那个结点
tips:报数钱 先让first和helper移动k-1次
即:让first移动到设定的开始报数的那个结点
2.当数数时 让first和helper同时移动m-1次
3.这是就可以将first指向的结点出圈
first = first.next;
helper.next=first
原来first指向的结点就没有任何引用就会被回收
代码:
public class yuesefu {public static void main(String[] args) {hxdxlb hx= new hxdxlb();hx.addP(125);hx.show();hx.chuquan(125,10,20);}}//创建一个环形的单向链表class hxdxlb{//创建一个first结点 当前没有编号privatep first = new p(-1);//添加p结点 构成环形链表public void addP(int num){if(num<1){System.out.println("太少了哥");return;}p curr = null;//辅助结点//使用for循环创建环形链表//从编号1开始到numfor (int i = 1; i <=num ; i++) {//根据编号创建p结点p pp = new p(i);if(i==1){first=pp;first.setNext(first);//构成环curr = first;//让curr指向第一个}else{curr.setNext(pp);pp.setNext(first);curr=pp;}}}//遍历环形链表public void show(){if(first==null){return;}//因为first不能动 所以需要使用辅助指针p curr = first;while (true){System.out.println("结点"+curr.getNo());if(curr.getNext()==first){break;}curr=curr.getNext();}}//出队// 比如: 5个人(n=5) 从第一个开始报数(k=1) 每数到2出去(m=2)publicvoid chuquan(int n,int k,int m){if(first==null||n<1||m>n){return;}p helper = first;while (true){if(helper.getNext()==first){break;}helper=helper.getNext();}for (int i = 0; i < k-1; i++) {first=first.getNext();helper=helper.getNext();}while(true){if(first==helper){System.out.println("最后留在圈中的结点:"+first.getNo());break;}for(int i=1;i<=m-1;i++){first=first.getNext();helper=helper.getNext();}System.out.println(first.getNo());first = first.getNext();helper.setNext(first);}}}class p{private int no;private p next;//指向下一个结点public p(int no) {this.no = no;}@Overridepublic String toString() {return "p{" +"no=" + no +'}';}public int getNo() {return no;}public void setNo(int no) {this.no = no;}public p getNext() {return next;}public void setNext(p next) {this.next = next;}}