微信
支付宝
# 1.3 链表（Linked List） #### 一. 定义 链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。链表由一系列节点（链表中每一个元素称为节点）组成，节点在运行时动态生成 （malloc），每个节点包括两个部分：一个是存储数据元素的\*\*数据域\*\*，另一个是存储下一个节点地址的\*\*指针域\*\*。 \* \*\*头结点：\*\* 为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个 结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，用于表示单链表头。头结点的指针域存储指向第一个结点的指针。头结点不一定是链表的必需要素。 \* \*\*头指针：\*\*头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。头指针具有标志作用，所以常用头指针冠以链表的名字。无论链表是否为空，头指针均不为空。头指针是链表的必要元素。 #### 二. 特点 !\[在这里插入图片描述\](https://img-blog.csdnimg.cn/2f56343aef6248eebc36d5bed39c2423.png) #### 三. 单链表的增删改查 \`\`\`java /\*\* \* desc:单链表的创建和应用 \* @author GreyPigeon mail:2371849349@qq.com \* @since 2024-01-08-22:18 \*\*/ public class SingleLinkedListDemo { 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, "林冲", "豹子头"); //创建要给链表 SingleLinkedList singleLinkedList = new SingleLinkedList(); //添加节点 // singleLinkedList.add(hero1); // singleLinkedList.add(hero4); // singleLinkedList.add(hero2); // singleLinkedList.add(hero3); //按照编号的顺序添加 singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero4); singleLinkedList.addByOrder(hero2); singleLinkedList.addByOrder(hero3); singleLinkedList.addByOrder(hero3); //显示链表 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 list(){ //判断链表是否为空 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; } } //第二种方式在添加英雄时，根据排名将英雄插入到指定位置 //(如果有这个排名，则添加失败，并给出提示) public void addByOrder(HeroNode heroNode) { //因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置 //因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了 HeroNode temp = head; boolean flag = false; // flag标志添加的编号是否存在，默认为false while(true) { if(temp.next == null) {//说明temp已经在链表的最后 break; } if(temp.next.no \> heroNode.no) { //位置找到，就在temp的后面插入 break; } else if (temp.next.no == heroNode.no) { //说明希望添加的heroNode的编号已然存在 flag = true; //说明编号存在 break; } temp = temp.next; //后移，遍历当前链表 } //判断flag 的值 if(flag) { //不能添加，说明编号存在 System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\\n", heroNode.no); } else { //插入到链表中, temp的后面 heroNode.next = temp.next; temp.next = heroNode; } } //修改节点的信息, 根据no编号来修改，即no编号不能改. //1. 根据 newHeroNode 的 no 来修改即可 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; } //根据flag 判断是否找到要修改的节点 if(flag) { temp.name = newHeroNode.name; temp.nickname = newHeroNode.nickname; } else { //没有找到 System.out.printf("没有找到 编号 %d 的节点，不能修改\\n", newHeroNode.no); } } //删除节点 //思路 //1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点 //2. 说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较 public void del(int no) { 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; //temp后移，遍历 } //判断flag if(flag) { //找到 //可以删除 temp.next = temp.next.next; }else { System.out.printf("要删除的 %d 节点不存在\\n", no); } } } //定义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 + '\\'' + '}'; } } \`\`\` #### 四. 练习 \`\`\`java /\*\* \*方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点) \* @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; } /\*\* \* 实现链表的逆序打印 \* 可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果 \* 栈的先进后出并不会改变单链表节点的结构 \* @param head \* @return void \*\*/ public static void reversePrint(HeroNode head){ if (head.next == null) { return; //空链表，不能打印 } //创建一个栈，将各个结点压入栈 Stack stack = new Stack\<\>(); HeroNode cur = head.next; //通过循环将链表中的所有结点压入栈中 while (cur != null) { stack.push(cur); //入栈：add()或push() cur = cur.next; //cur后移 } //将栈中的结点进行打印，出栈：pop() while (stack.size() \> 0) { System.out.println(stack.pop()); //stack的特点是先进后出 } } /\*\* \* 将单链表反转 \* @param head \* @return void \*\*/ public static void reversetList(HeroNode head) { //如果当前链表为空，或者只有一个节点，无需反转，直接返回 if(head.next == null \|\| head.next.next == null) { return ; } //定义一个辅助的指针(变量)，帮助我们遍历原来的链表 HeroNode cur = head.next; HeroNode next = null;// 指向当前节点\[cur\]的下一个节点 HeroNode reverseHead = new HeroNode(0, "", ""); //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端 while(cur != null) { next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用 cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端 reverseHead.next = cur; //将cur 连接到新的链表上 cur = next;//让cur后移 } //最后将head.next 指向 reverseHead.next , 实现单链表的反转 head.next = reverseHead.next; } /\*\* \* 查找单链表中的倒数第k个结点 【新浪面试题】 \* 思路 \* 1. 编写一个方法，接收head节点，同时接收一个index \* 2. index 表示是倒数第index个节点 \* 3. 先把链表从头到尾遍历，得到链表的总的长度 getLength \* 4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到 \* 5. 如果找到了，则返回该节点，否则返回nulll \* @param head \* @param index \* @return com.hgh.linkedlist.HeroNode \*\*/ public static HeroNode findLastIndexNode(HeroNode head, int index) { //判断如果链表为空，返回null if(head.next == null) { return null;//没有找到 } //第一个遍历得到链表的长度(节点个数) int size = getLength(head); //第二次遍历 size-index 位置，就是我们倒数的第K个节点 //先做一个index的校验 if(index \<=0 \|\| index \> size) { return null; } //定义给辅助变量， for 循环定位到倒数的index HeroNode cur = head.next; //3 // 3 - 1 = 2 for(int i =0; i\< size - index; i++) { cur = cur.next; } return cur; } } \`\`\` #### 五. 单向链表完整代码 \`\`\`java /\*\* \* desc:单链表的创建和应用 \* @author GreyPigeon mail:2371849349@qq.com \* @since 2024-01-08-22:18 \*\*/ public class SingleLinkedListDemo { 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, "林冲", "豹子头"); //创建要给链表 SingleLinkedList singleLinkedList = new SingleLinkedList(); //添加节点 // singleLinkedList.add(hero1); // singleLinkedList.add(hero4); // singleLinkedList.add(hero2); // singleLinkedList.add(hero3); //按照编号的顺序添加 singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero4); singleLinkedList.addByOrder(hero2); singleLinkedList.addByOrder(hero3); singleLinkedList.addByOrder(hero3); //显示链表 singleLinkedList.list(); //测试1：求单链表中有效节点的个数 System.out.println("有效的结点个数为：" + getLength(singleLinkedList.getHead())); //测试2：获取倒数第k个结点 HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 3); System.out.println("res: " + res); // 测试3：:单链表的反转功能 System.out.println("原来链表的情况\~\~"); singleLinkedList.list(); System.out.println("反转单链表\~\~"); reversetList(singleLinkedList.getHead()); singleLinkedList.list(); // 测试4：:逆序打印单链表 System.out.println("逆序打印单链表(但不改变单链表的结构）"); reversePrint(singleLinkedList.getHead()); } /\*\* \*方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点) \* @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; } /\*\* \* 实现链表的逆序打印 \* 可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果 \* 栈的先进后出并不会改变单链表节点的结构 \* @param head \* @return void \*\*/ public static void reversePrint(HeroNode head){ if (head.next == null) { return; //空链表，不能打印 } //创建一个栈，将各个结点压入栈 Stack stack = new Stack\<\>(); HeroNode cur = head.next; //通过循环将链表中的所有结点压入栈中 while (cur != null) { stack.push(cur); //入栈：add()或push() cur = cur.next; //cur后移 } //将栈中的结点进行打印，出栈：pop() while (stack.size() \> 0) { System.out.println(stack.pop()); //stack的特点是先进后出 } } /\*\* \* 将单链表反转 \* @param head \* @return void \*\*/ public static void reversetList(HeroNode head) { //如果当前链表为空，或者只有一个节点，无需反转，直接返回 if(head.next == null \|\| head.next.next == null) { return ; } //定义一个辅助的指针(变量)，帮助我们遍历原来的链表 HeroNode cur = head.next; HeroNode next = null;// 指向当前节点\[cur\]的下一个节点 HeroNode reverseHead = new HeroNode(0, "", ""); //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端 while(cur != null) { next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用 cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端 reverseHead.next = cur; //将cur 连接到新的链表上 cur = next;//让cur后移 } //最后将head.next 指向 reverseHead.next , 实现单链表的反转 head.next = reverseHead.next; } /\*\* \* 查找单链表中的倒数第k个结点 【新浪面试题】 \* 思路 \* 1. 编写一个方法，接收head节点，同时接收一个index \* 2. index 表示是倒数第index个节点 \* 3. 先把链表从头到尾遍历，得到链表的总的长度 getLength \* 4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到 \* 5. 如果找到了，则返回该节点，否则返回nulll \* @param head \* @param index \* @return com.hgh.linkedlist.HeroNode \*\*/ public static HeroNode findLastIndexNode(HeroNode head, int index) { //判断如果链表为空，返回null if(head.next == null) { return null;//没有找到 } //第一个遍历得到链表的长度(节点个数) int size = getLength(head); //第二次遍历 size-index 位置，就是我们倒数的第K个节点 //先做一个index的校验 if(index \<=0 \|\| index \> size) { return null; } //定义给辅助变量， for 循环定位到倒数的index HeroNode cur = head.next; //3 // 3 - 1 = 2 for(int i =0; i\< size - index; i++) { cur = cur.next; } return cur; } } //定义SingleLinkedList 单向链表来管理英雄 class SingleLinkedList{ //先初始化一个头结点, 头结点不要动, 不存放具体的数据 private HeroNode head = new HeroNode(0, "", ""); public HeroNode getHead() { return head; } //添加节点到单向链表 //思路，当不考虑编号顺序时 //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 list(){ //判断链表是否为空 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; } } //第二种方式在添加英雄时，根据排名将英雄插入到指定位置 //(如果有这个排名，则添加失败，并给出提示) public void addByOrder(HeroNode heroNode) { //因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置 //因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了 HeroNode temp = head; boolean flag = false; // flag标志添加的编号是否存在，默认为false while(true) { if(temp.next == null) {//说明temp已经在链表的最后 break; } if(temp.next.no \> heroNode.no) { //位置找到，就在temp的后面插入 break; } else if (temp.next.no == heroNode.no) { //说明希望添加的heroNode的编号已然存在 flag = true; //说明编号存在 break; } temp = temp.next; //后移，遍历当前链表 } //判断flag 的值 if(flag) { //不能添加，说明编号存在 System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\\n", heroNode.no); } else { //插入到链表中, temp的后面 heroNode.next = temp.next; temp.next = heroNode; } } //修改节点的信息, 根据no编号来修改，即no编号不能改. //1. 根据 newHeroNode 的 no 来修改即可 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; } //根据flag 判断是否找到要修改的节点 if(flag) { temp.name = newHeroNode.name; temp.nickname = newHeroNode.nickname; } else { //没有找到 System.out.printf("没有找到 编号 %d 的节点，不能修改\\n", newHeroNode.no); } } //删除节点 //思路 //1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点 //2. 说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较 public void del(int no) { 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; //temp后移，遍历 } //判断flag if(flag) { //找到 //可以删除 temp.next = temp.next.next; }else { System.out.printf("要删除的 %d 节点不存在\\n", no); } } } //定义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 + '\\'' + '}'; } } \`\`\` #### 六. 双向链表(double linkde list) 双向链表是在单链表的每个结点中，在设置一个指向其前驱结点的指针域。双向链表是单链表中扩展出来的结构，所以它的很多操作是和单链表相同的（只涉及到一个方向的指针：如查找，求长度）。 \*\*双向链表与单向链表的区别：\*\*单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。单向链表怀能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除时，节点总是找到temp,temp是待删除节点的前一个节点。 !\[链表2\](https://code-thinking-1253855093.file.myqcloud.com/pics/20200806194559317.png) \*\*具体代码如下：\*\* \`\`\`java /\*\* \* desc: 双向链表的创建和应用 \* @author GreyPigeon mail:2371849349@qq.com \* @since 2024-01-09-17:16 \*\*/ public class DoubleLinkedListDemo { public static void main(String\[\] args) { // 测试 System.out.println("双向链表的测试"); // 先创建节点 HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨"); HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟"); HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星"); HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头"); // 创建一个双向链表 DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); doubleLinkedList.add(hero1); doubleLinkedList.add(hero2); doubleLinkedList.add(hero3); doubleLinkedList.add(hero4); doubleLinkedList.list(); // 修改 HeroNode2 newHeroNode = new HeroNode2(4, "公孙胜", "入云龙"); doubleLinkedList.update(newHeroNode); System.out.println("修改后的链表情况"); doubleLinkedList.list(); // 删除 doubleLinkedList.del(3); System.out.println("删除后的链表情况\~\~"); doubleLinkedList.list(); } } // 创建一个双向链表的类 class DoubleLinkedList { // 先初始化一个头节点, 头节点不要动, 不存放具体的数据 private HeroNode2 head = new HeroNode2(0, "", ""); // 返回头节点 public HeroNode2 getHead() { return head; } // 遍历双向链表的方法 // 显示链表\[遍历\] 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); // 将temp后移， 一定小心 temp = temp.next; } } // 添加一个节点到双向链表的最后. public void add(HeroNode2 heroNode) { // 因为head节点不能动，因此我们需要一个辅助遍历 temp HeroNode2 temp = head; // 遍历链表，找到最后 while (true) { // 找到链表的最后 if (temp.next == null) {// break; } // 如果没有找到最后, 将将temp后移 temp = temp.next; } // 当退出while循环时，temp就指向了链表的最后 // 形成一个双向链表 temp.next = heroNode; heroNode.pre = temp; } // 修改一个节点的内容, 可以看到双向链表的节点内容修改和单向链表一样 // 只是 节点类型改成 HeroNode2 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; } // 根据flag 判断是否找到要修改的节点 if (flag) { temp.name = newHeroNode.name; temp.nickname = newHeroNode.nickname; } else { // 没有找到 System.out.printf("没有找到 编号 %d 的节点，不能修改\\n", newHeroNode.no); } } // 从双向链表中删除一个节点, // 说明 // 1 对于双向链表，我们可以直接找到要删除的这个节点 // 2 找到后，自我删除即可 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; // temp后移，遍历 } // 判断flag if (flag) { // 找到 // 可以删除 // temp.next = temp.next.next;\[单向链表\] temp.pre.next = temp.next; // 这里我们的代码有问题? // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针 if (temp.next != null) { temp.next.pre = temp.pre; } } else { System.out.printf("要删除的 %d 节点不存在\\n", no); } } } // 定义HeroNode2 ， 每个HeroNode 对象就是一个节点 class HeroNode2 { public int no; public String name; public String nickname; public HeroNode2 next; // 指向下一个节点, 默认为null public HeroNode2 pre; // 指向前一个节点, 默认为null // 构造器 public HeroNode2(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 + "\]"; } } \`\`\` \*\*练习案例\*\* \`\`\`java /\*\* \* 在添加英雄时，根据排名将英雄插入到指定位置 \* (如果有这个排名，则添加失败，并给出提示) \* @param heroNode \* @return void \*\*/ public void addByOrder(HeroNode2 heroNode) { //因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置 //因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了 HeroNode2 temp = head; boolean flag = false; // flag标志添加的编号是否存在，默认为false while(true) { if(temp.next == null) {//说明temp已经在链表的最后 break; } if(temp.next.no \> heroNode.no) { //位置找到，就在temp的后面插入 break; } else if (temp.next.no == heroNode.no) { //说明希望添加的heroNode的编号已然存在 flag = true; //说明编号存在 break; } temp = temp.next; //后移，遍历当前链表 } //判断flag 的值 if(flag) { //不能添加，说明编号存在 System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\\n", heroNode.no); } else { //插入到链表中, temp的后面 heroNode.pre = temp; heroNode.next = temp.next; if (temp.next != null) { temp.next.pre = heroNode; } temp.next = heroNode; } } \`\`\` #### 八. （单向）循环链表 将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（circular linked list）。 \*\*创建一个循环链表\*\* \* 先创建第一个节点，让first指向该节点，并形成环形 \* 每创建一个新的节点，就把该节点，加入到已有的环形链表中即可。 \*\*遍历循环链表\*\* \* 先让一个辅助指针（变量）temp,指向frst结点。 \* 然后通过一个while循环遍历该循环链表即可，当temp = first时结束循环。 循环链表可以用来解决约瑟夫环问题。  \*\*练习案例\*\* \`\`\`java /\*\* \* desc: Josephu(约瑟夫、约瑟夫环) 问题 \* Josephu 问题为：设编号为1，2，... n的n个人围坐一圈，约定编号为k（1\<=k\<=n）的人从1开始报数，数到m的那个人出列， \* 它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。 \* 步骤 \* 1.需要创建一个辅助指针（变量）helper,事先应该指向环形链表的最后这个节点。 \* 2.当小孩报数前，让first和helper移动 k-1 次 \* 3.当小孩报数时，让first和helper指针同时的移动m-1次 \* 4.这时就可以将t指向的小孩节点出圈：first first.next，helper.next =first \* （原来ist指向的节点就没有任何引用，就会被回收） \* @author GreyPigeon mail:2371849349@qq.com \* @since 2024-01-09-21:58 \*\*/ public class Josepfu { public static void main(String\[\] args) { // 测试循环链表 CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(); circleSingleLinkedList.addBoy(125);// 加入num个小孩节点 circleSingleLinkedList.showBoy(); //测试小孩出圈是否正确 circleSingleLinkedList.countBoy(10, 20, 125); } } // 创建一个单向循环链表 class CircleSingleLinkedList { // 创建一个first节点,当前没有编号 private Boy first = null; // 添加小孩节点，构建成一个环形的链表 public void addBoy(int nums) { // nums 做一个数据校验 if (nums \< 1) { System.out.println("nums的值不正确"); 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指向第一个小孩 } 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 \\n", curBoy.getNo()); if (curBoy.getNext() == first) {// 说明已经遍历完毕 break; } curBoy = curBoy.getNext(); // curBoy后移 } } /\*\* \* 根据用户的输入，计算出小孩出圈的顺序 \* @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; } // 创建要给辅助指针,帮助完成小孩出圈 Boy helper = first; // 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点 while (true) { if (helper.getNext() == first) { // 说明helper指向最后小孩节点 break; } helper = helper.getNext(); } //小孩报数前，先让 first 和 helper 移动 k - 1次 for(int j = 0; j \< startNo - 1; j++) { first = first.getNext(); helper = helper.getNext(); } //当小孩报数时，让first 和 helper 指针同时 的移动 m - 1 次, 然后出圈 //这里是一个循环操作，知道圈中只有一个节点 while(true) { if(helper == first) { //说明圈中只有一个节点 break; } //让 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 \\n", first.getNo()); } } // 创建一个Boy类，表示一个节点 class Boy { private int no;// 编号 private Boy next; // 指向下一个节点,默认null 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; } } \`\`\` \> 参考自：《大话数据结构》、尚硅谷
本文是原创文章，采用 CC BY-NC-ND 4.0 协议，完整转载请注明来自 Veylor
最近发布
![常用SQL]()
常用SQL
