Java数据结构与算法_02 链表 （约瑟夫问题）
本文共 22500 字，大约阅读时间需要 75 分钟。
Java数据结构与算法_02
本人是个新手，写下博客用于自我复习、自我总结。 如有错误之处，请各位大佬指出。 学习资料来源于：尚硅谷
单向链表
链表是有序的列表，但是它在内存中是存储如下：
链表是以节点的方式来存储的，每个节点包含 data 域， next 域，data用来存放数据，next用来指向下一个节点。正因为这种特性，链表的各个节点不一定是连续存储。链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定。 单链表(带头结点) 逻辑结构示意图如下:
头结点实际上不存放具体的数据，作用就是表示单链表。 添加数据（创建）
添加数据有两种情况，
第一种是：创建一个head 头节点， 之后每添加一个节点，就直接加入到链表的最后。 第二种是：创建一个head 头节点， 之后按照一些顺序（比如编号）把节点添加到链表的相应位置上。第一种的思路是：
1.首先找到当前链表的最后节点。这就需要遍历寻找最后节点。显然，这就需要从头节点开始遍历，但是由于头节点本身不能动，所以就可以通过一个辅助变量，来帮助遍历整个链表。 2.找到了最后的节点之后，只要将最后这个节点的next 指向 新的节点 即可。第二种的思路是：
1.首先找到新添加的节点的位置。通过辅助变量temp的遍历来完成。需要注意的是，这个 temp 需要位于 添加位置的前一个节点，否则插入不了。（因为是单向链表） 2.找到位置之后，新的节点的next 只要指向 temp.next ，再将temp.next 指向 新的节点 即可。// 添加节点到单向链表，不考虑编号顺序时 public void add(Node newNode) { // 因为head节点不能动，因此我们需要辅助变量temp来遍历 Node temp = head; // 遍历链表，找到最后 while (true) { // 如果找到了链表的最后 if (temp.next == null) { break; } // 如果没有找到最后, 将将temp后移 temp = temp.next; } // 当退出while循环时，temp就指向了链表的最后 // 将最后这个节点的next 指向 新的节点 temp.next = newNode; } // 添加节点到单向链表，考虑编号顺序时 // (如果对应编号上，有数据，则添加失败) public void addByOrder(Node newNode) { // 因为头节点不能动，因此仍然通过一个辅助变量来找到添加的位置 // 这个 temp 需要位于 添加位置的前一个节点，否则插入不了 Node temp = head; boolean flag = false; // 判断添加的编号是否存在，默认为false while (true) { // 当temp已经在链表的最后，退出即可。因为新节点肯定在最后 if (temp.next == null) { break; } // 位置找到，就在temp的后面插入 if (temp.next.no > newNode.no) { break; } // 说明希望添加的节点的编号已经存在 else if (temp.next.no == newNode.no) { flag = true; // 说明编号存在 break; } temp = temp.next; // 后移，遍历当前链表 } // 判断flag的值 // 不能添加，说明编号存在 if (flag) { System.out.printf("准备插入的编号 %d 已经存在了, 不能加入\n", newNode.no); } // 可以插入 else { // 插入到链表中, temp的后面 newNode.next = temp.next; temp.next = newNode; } } 修改节点信息
即然想修改节点信息，肯定就要想怎么找到想修改的节点。肯定还是用辅助变量temp来遍历。所以在设计节点的时候，除了data和next，还可以设计一个no编号，或者设计其他的一些用来判断的。
// 修改节点的信息, 根据no编号来修改 public void update(Node newNode) { // 判断是否为空 if (head.next == null) { System.out.println("链表为空~"); return; } // 找到需要修改的节点, 根据no编号 // 定义一个辅助变量 Node temp = head.next; boolean flag = false; // 表示是否找到该节点 while (true) { if (temp == null) { break; // 已经遍历完链表 } if (temp.no == newNode.no) { // 找到 flag = true; break; } temp = temp.next; } // 根据flag 判断是否找到要修改的节点 if (flag) { temp.data = newNode.data; } // 没有找到 else { System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newNode.no); } } 删除节点信息
首先找到需要删除的这个节点的前一个节点 temp，依然使用辅助变量。确定到这个位置，只需要让temp.next.no 和 需要删除的节点的no比较。确定好位置后，让temp.next 指向 temp.next.next即可。被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收。
// 删除节点 public void del(int no) { Node 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); } } 完整代码
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(hero4); singleLinkedList.add(hero2); singleLinkedList.add(hero3); /* 按照编号的顺序加入 * singleLinkedList.addByOrder(hero1); * singleLinkedList.addByOrder(hero4); * singleLinkedList.addByOrder(hero2); * singleLinkedList.addByOrder(hero3); * */ /* 修改节点 * HeroNode newNode = new Node(2, "小卢"); * singleLinkedList.update(newNode); * */ /* 删除节点 * singleLinkedList.del(1); */ System.out.println("链表："); singleLinkedList.list(); }}// 定义SingleLinkedList 对数据进行操作class SingleLinkedList { // 先初始化一个头节点, 头节点不能动, 不存放具体的数据 private Node head = new Node(0, ""); // 返回头节点 public Node getHead() { return head; } // 添加节点到单向链表，不考虑编号顺序时 public void add(Node newNode) { // 因为head节点不能动，因此我们需要辅助变量temp来遍历 Node temp = head; // 遍历链表，找到最后 while (true) { // 如果找到了链表的最后 if (temp.next == null) { break; } // 如果没有找到最后, 将将temp后移 temp = temp.next; } // 当退出while循环时，temp就指向了链表的最后 // 将最后这个节点的next 指向 新的节点 temp.next = newNode; } // 添加节点到单向链表，考虑编号顺序时 // (如果对应编号上，有数据，则添加失败) public void addByOrder(Node newNode) { // 因为头节点不能动，因此仍然通过一个辅助变量来找到添加的位置 // 这个 temp 需要位于 添加位置的前一个节点，否则插入不了 Node temp = head; boolean flag = false; // 判断添加的编号是否存在，默认为false while (true) { // 当temp已经在链表的最后，退出即可。因为新节点肯定在最后 if (temp.next == null) { break; } // 位置找到，就在temp的后面插入 if (temp.next.no > newNode.no) { break; } // 说明希望添加的节点的编号已经存在 else if (temp.next.no == newNode.no) { flag = true; // 说明编号存在 break; } temp = temp.next; // 后移，遍历当前链表 } // 判断flag的值 // 不能添加，说明编号存在 if (flag) { System.out.printf("准备插入的编号 %d 已经存在了, 不能加入\n", newNode.no); } // 可以插入 else { // 插入到链表中, temp的后面 newNode.next = temp.next; temp.next = newNode; } } // 修改节点的信息, 根据no编号来修改 public void update(Node newNode) { // 判断是否为空 if (head.next == null) { System.out.println("链表为空~"); return; } // 找到需要修改的节点, 根据no编号 // 定义一个辅助变量 Node temp = head.next; boolean flag = false; // 表示是否找到该节点 while (true) { if (temp == null) { break; // 已经遍历完链表 } if (temp.no == newNode.no) { // 找到 flag = true; break; } temp = temp.next; } // 根据flag 判断是否找到要修改的节点 if (flag) { temp.data = newNode.data; } // 没有找到 else { System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newNode.no); } } // 删除节点 public void del(int no) { Node 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); } } // 显示链表[遍历] public void list() { // 判断链表是否为空 if (head.next == null) { System.out.println("链表为空"); return; } // 因为头节点不能动，因此我们需要一个辅助变量来遍历 Node temp = head.next; while (true) { // 判断是否到链表最后 if (temp == null) { break; } // 输出节点的信息 System.out.println(temp); // 将temp后移， 一定小心 temp = temp.next; } }}// 定义Node ， 每个Node对象就是一个节点class Node { public int no; public String data; public Node next; // 指向下一个节点 // 构造器 public Node(int no, String data) { this.no = no; this.data = data; } @Override public String toString() { return "Node [no=" + no + "，data=" + data + "]"; }} 面试题
第一题很简单，只需要找一个辅助变量，像之前一样遍历即可，再加一个变量用来计数。只要辅助变量的next为null就停止。只需要注意头节点应不应该计算在内。
第二题：
1.编写一个方法，接收head节点，同时接收一个index。这个index 表示的是倒数第index个节点。
2.先把链表从头到尾遍历，得到链表的总的长度 size。利用第一题就可以得到。依然不包括头节点。
3.判断index是否满足条件：index <= 0 || index > size 。满足这个条件，显然不符合标准，返回null即可。
4.满足了条件之后，我们依然利用辅助变量，从链表的头节点后的第一个节点开始遍历，遍历 size-index 次，就可以得到该节点。
（假如链表不包括头节点，有5个节点，倒数第4个节点，就是正数第2个节点，即从第一个节点开始遍历，遍历5-4=1次，让辅助变量遍历到第2个节点并返回即可）
（当然遍历的条件和方式有很多种，可以自行变换）
5.如果找到了，则返回该节点，否则返回null
第三题：
1.首先，如果当前链表为空，或者只有一个节点，无需反转，直接返回。
2.定义一个新的头节点 reverseHead，用来记录反转后的链表。
3.从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端。
4.最后，让原来的链表的head.next = reverseHead.next，就完成了转换。
第四题：
逆序打印单链表有两种方式，
方式1： 先将单链表进行反转操作，然后再遍历即可，这样的做的问题是会破坏原来的单链表的结构，就像第三题那样。
方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果。
对于方式2，就很简单了，只要知道栈的基本用法就可以实现：
（现在先简单说明）import java.util.Stack;//演示栈Stack的基本使用public class TestStack { public static void main(String[] args) { Stack stack = new Stack(); // 入栈 stack.add("jack"); stack.add("tom"); stack.add("smith"); // 出栈 while (stack.size() > 0) { System.out.println(stack.pop());//pop就是将栈顶的数据取出 } }} 完整代码
import java.util.Stack;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(hero4); singleLinkedList.add(hero2); singleLinkedList.add(hero3); /* * 按照编号的顺序加入 singleLinkedList.addByOrder(hero1); * singleLinkedList.addByOrder(hero4); * singleLinkedList.addByOrder(hero2); * singleLinkedList.addByOrder(hero3); */ /* * 修改节点 HeroNode newNode = new Node(2, "小卢"); * singleLinkedList.update(newNode); */ /* * 删除节点 singleLinkedList.del(1); */ System.out.println("原来链表的情况："); singleLinkedList.list(); /* * 求单链表中有效节点的个数 * System.out.println("有效的节点个数=" +getLength(singleLinkedList.getHead())); * * 得到倒数第K个节点 * Node res = findLastIndexNode(singleLinkedList.getHead(),3); * System.out.println("res=" + res); */ // System.out.println("反转单链表："); // reverseList(singleLinkedList.getHead()); // singleLinkedList.list(); System.out.println("逆序打印单链表, 没有改变链表的结构："); reversePrint(singleLinkedList.getHead()); } // 题目一：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点) public static int getLength(Node head) { if (head.next == null) { // 空链表 return 0; } int length = 0; // 定义一个辅助的变量，不计算头节点 Node cur = head.next; while (cur != null) { length++; cur = cur.next; // 遍历 } return length; } // 题目二：查找单链表中的倒数第k个结点 public static Node findLastIndexNode(Node head, int index) { // 如果链表为空，返回null if (head.next == null) { return null; } // 第一个遍历得到链表的长度(节点个数) int size = getLength(head); // 先做一个index的校验 if (index <= 0 || index > size) { return null; } // 第二次遍历到 size-index 位置，就是倒数的第K个节点 // 定义辅助变量， 定位到倒数的index Node cur = head.next; for (int i = 0; i < size - index; i++) { cur = cur.next; } return cur; } // 题目三：将单链表反转 public static void reverseList(Node head) { // 如果当前链表为空，或者只有一个节点，无需反转，直接返回 if (head.next == null || head.next.next == null) { return; } // 定义一个辅助变量，帮助遍历原来的链表 Node cur = head.next; Node next = null;// 指向当前节点[cur]的下一个节点 Node reverseHead = new Node(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; } // 题目四的方式2： // 可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果 public static void reversePrint(Node head) { if (head.next == null) { return;// 空链表，不能打印 } // 创建一个栈，将各个节点压入栈 Stack stack = new Stack (); Node cur = head.next; // 将链表的所有节点压入栈 while (cur != null) { stack.push(cur); cur = cur.next; // cur后移，这样就可以压入下一个节点 } // 将栈中的节点进行打印,pop 出栈 while (stack.size() > 0) { System.out.println(stack.pop()); // stack的特点是先进后出 } }}// 定义SingleLinkedList 对数据进行操作class SingleLinkedList { // 先初始化一个头节点, 头节点不能动, 不存放具体的数据 private Node head = new Node(0, ""); // 返回头节点 public Node getHead() { return head; } // 添加节点到单向链表，不考虑编号顺序时 public void add(Node newNode) { // 因为head节点不能动，因此我们需要辅助变量temp来遍历 Node temp = head; // 遍历链表，找到最后 while (true) { // 如果找到了链表的最后 if (temp.next == null) { break; } // 如果没有找到最后, 将将temp后移 temp = temp.next; } // 当退出while循环时，temp就指向了链表的最后 // 将最后这个节点的next 指向 新的节点 temp.next = newNode; } // 添加节点到单向链表，考虑编号顺序时 // (如果对应编号上，有数据，则添加失败) public void addByOrder(Node newNode) { // 因为头节点不能动，因此仍然通过一个辅助变量来找到添加的位置 // 这个 temp 需要位于 添加位置的前一个节点，否则插入不了 Node temp = head; boolean flag = false; // 判断添加的编号是否存在，默认为false while (true) { // 当temp已经在链表的最后，退出即可。因为新节点肯定在最后 if (temp.next == null) { break; } // 位置找到，就在temp的后面插入 if (temp.next.no > newNode.no) { break; } // 说明希望添加的节点的编号已经存在 else if (temp.next.no == newNode.no) { flag = true; // 说明编号存在 break; } temp = temp.next; // 后移，遍历当前链表 } // 判断flag的值 // 不能添加，说明编号存在 if (flag) { System.out.printf("准备插入的编号 %d 已经存在了, 不能加入\n", newNode.no); } // 可以插入 else { // 插入到链表中, temp的后面 newNode.next = temp.next; temp.next = newNode; } } // 修改节点的信息, 根据no编号来修改 public void update(Node newNode) { // 判断是否为空 if (head.next == null) { System.out.println("链表为空~"); return; } // 找到需要修改的节点, 根据no编号 // 定义一个辅助变量 Node temp = head.next; boolean flag = false; // 表示是否找到该节点 while (true) { if (temp == null) { break; // 已经遍历完链表 } if (temp.no == newNode.no) { // 找到 flag = true; break; } temp = temp.next; } // 根据flag 判断是否找到要修改的节点 if (flag) { temp.data = newNode.data; } // 没有找到 else { System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newNode.no); } } // 删除节点 public void del(int no) { Node 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); } } // 显示链表[遍历] public void list() { // 判断链表是否为空 if (head.next == null) { System.out.println("链表为空"); return; } // 因为头节点不能动，因此我们需要一个辅助变量来遍历 Node temp = head.next; while (true) { // 判断是否到链表最后 if (temp == null) { break; } // 输出节点的信息 System.out.println(temp); // 将temp后移， 一定小心 temp = temp.next; } }}// 定义Node ， 每个Node对象就是一个节点class Node { public int no; public String data; public Node next; // 指向下一个节点 // 构造器 public Node(int no, String data) { this.no = no; this.data = data; } @Override public String toString() { return "Node [no=" + no + "，data=" + data + "]"; }} 双向链表
单向链表有一些缺点：
（1）单向链表查找的方向只能是一个方向，而双向链表可以向前或者向后查找；
（2）单向链表不能自我删除，需要靠辅助节点。而双向链表，则可以自我删除。这也就是为什么之前单链表删除节点时，总是需要先找到待删除节点的前一个节点。
也就是说，双向链表是对单向链表的改进，不仅可以记录数据和下一个节点，现在又可以记录上一个节点。
对双向链表的操作和对单向链表的操作，没有太大的不同，就是注意需要指向上一个节点即可。
完整代码
public class DoubleLinkedListDemo { public static void main(String[] args) { // 创建节点 Node2 hero1 = new Node2(1, "宋江"); Node2 hero2 = new Node2(2, "卢俊义"); Node2 hero3 = new Node2(3, "吴用"); Node2 hero4 = new Node2(4, "林冲"); // 创建一个双向链表 DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); doubleLinkedList.addByOrder(hero4); doubleLinkedList.addByOrder(hero2); doubleLinkedList.addByOrder(hero3); doubleLinkedList.addByOrder(hero1); System.out.println("原来链表的情况："); doubleLinkedList.list(); // 修改 Node2 newNode = new Node2(4, "公孙胜"); doubleLinkedList.update(newNode); System.out.println("修改后的链表情况"); doubleLinkedList.list(); // 删除 doubleLinkedList.del(3); System.out.println("删除后的链表情况"); doubleLinkedList.list(); }}// 创建一个双向链表的类class DoubleLinkedList { // 先初始化一个头节点, 头节点不要动, 不存放具体的数据 private Node2 head = new Node2(0, ""); // 返回头节点 public Node2 getHead() { return head; } // 遍历双向链表的方法 // 显示链表[遍历] public void list() { // 判断链表是否为空 if (head.next == null) { System.out.println("链表为空"); return; } // 因为头节点不能动，因此我们需要一个辅助变量来遍历 Node2 temp = head.next; while (true) { // 判断是否到链表最后 if (temp == null) { break; } // 输出节点的信息 System.out.println(temp); // 将temp后移， 一定小心 temp = temp.next; } } // 添加一个节点到双向链表的最后 public void add(Node2 newNode) { // 因为头节点不能动，因此我们需要一个辅助变量来遍历 Node2 temp = head; // 遍历链表，找到最后 while (true) { // 找到链表的最后 if (temp.next == null) { break; } // 如果没有找到最后, 将将temp后移 temp = temp.next; } // 当退出while循环时，temp就指向了链表的最后 // 形成一个双向链表 temp.next = newNode; newNode.pre = temp; } // 添加节点到双向链表，考虑编号顺序时 // (如果对应编号上，有数据，则添加失败) public void addByOrder(Node2 newNode) { // 因为头节点不能动，因此仍然通过一个辅助变量来找到添加的位置 Node2 temp = head; boolean flag = false; // 判断添加的编号是否存在，默认为false while (true) { // 当temp已经在链表的最后，退出即可。因为新节点肯定在最后 if (temp.next == null) { break; } // 位置找到，就在temp的后面插入 if (temp.next.no > newNode.no) { break; } // 说明希望添加的节点的编号已经存在 else if (temp.next.no == newNode.no) { flag = true; // 说明编号存在 break; } temp = temp.next; // 后移，遍历当前链表 } // 判断flag的值 // 不能添加，说明编号存在 if (flag) { System.out.printf("准备插入的编号 %d 已经存在了, 不能加入\n", newNode.no); } // 可以插入 else { // 插入到链表中, 形成双向链表 newNode.next = temp.next; newNode.pre = temp; // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针 if (temp.next != null) { temp.next.pre = newNode; } temp.next = newNode; } } // 修改一个节点的内容, 可以看到双向链表的节点内容修改和单向链表一样 // 只是 节点类型改成 Node2 public void update(Node2 newNode) { // 判断是否空 if (head.next == null) { System.out.println("链表为空~"); return; } // 找到需要修改的节点, 根据no编号 // 定义一个辅助变量 Node2 temp = head.next; boolean flag = false; // 表示是否找到该节点 while (true) { if (temp == null) { break; // 已经遍历完链表 } if (temp.no == newNode.no) { // 找到 flag = true; break; } temp = temp.next; } // 根据flag 判断是否找到要修改的节点 if (flag) { temp.data = newNode.data; } else { // 没有找到 System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newNode.no); } } // 从双向链表中删除一个节点 public void del(int no) { // 判断当前链表是否为空 if (head.next == null) { // 空链表 System.out.println("链表为空，无法删除"); return; } Node2 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.pre.next = temp.next; // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针 if (temp.next != null) { temp.next.pre = temp.pre; } } else { System.out.printf("要删除的 %d 节点不存在\n", no); } }}// 定义Node2 ， 每个Node对象就是一个节点class Node2 { public int no; public String data; public Node2 next; // 指向下一个节点, 默认为null public Node2 pre; // 指向前一个节点, 默认为null // 构造器 public Node2(int no, String data) { this.no = no; this.data = data; } @Override public String toString() { return "Node [no=" + no + ", data=" + data + "]"; }} 单向环形链表（约瑟夫问题）
Josephu 问题：
设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
分析：
用一个不带头结点的循环链表可以处理Josephu 问题。
（1）构建一个单向的环形链表思路：
①先创建第一个节点，再建一个 first 节点，让 first 指向该节点。first ，就类似于链表的头节点的作用，找到这个单向环形链表的第一个节点 。
②再让它自己的 next 指向它自己，形成一个环形。 ③之后，当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可。（就相当于单向链表直接在链表尾部添加节点，只不过这个最后一个节点还有它的指向，即指向第一个节点）（2）遍历环形链表思路：
①先让一个辅助变量 cur，指向first节点 。
②然后通过一个while循环遍历 该环形链表即可 。直到 cur.next == first 结束 。（3）对于本问题，还需要一些其他的考虑。first 的指向需要一直移动。因为经过循环很有可能会删除first指向的节点，从而导致判断出现问题。因为我们判断什么时候结束，需要看链表什么时候为空，以前是判断head.next==null即可，而且是存在头指针的。但是假如这里使用判断为空的方法，又需要判断它是最后一个节点，因为如果不判断，像之前单向链表一样，我们所谓的删除就只是移动next指针，把要删除的节点移出，不是“真删除”，当只剩一个节点时，因为它是循环的，所以它的next总有值，所以需要判断它是最后一个节点，这样就意味着算法结束。这样显然很麻烦。不如在最开始时，就添加一个，可以指向最后一个节点的变量（指针）。 什么时候结束，只需要判断，当最后一个节点指针的指向 和 第一个指针的指向 都 指向了同一个节点，那也就意味着只有一个节点，也就意味着结束。
（4）所以，我们创建一个辅助指针(变量) helper ， 事先指向环形链表的最后一个节点。那么，算法开始时，先让 first 和 helper 移动 k - 1次。当小孩报数时，让first 和 helper 指针同时 的移动 m - 1 次。这时将first 指向的小孩节点出圈：
first = first .next helper.next = first （原来first 指向的节点就没有任何引用，就会被回收） 直到 first==helper 就结束了。比如：
一共5个小孩，编号为：1、2、3、4、5。现在first指向第1个小孩，helper指向第5个小孩。现在从第1个小孩开始，当报数为2时，这个小孩出列。算法开始时，先让 first 和 helper 移动 k - 1次。当小孩报数时，让first 和 helper 指针同时 的移动 m - 1 次。这时将first 指向的小孩节点出列，然后：first = first .next helper.next = first 直到 first==helper 就结束了。
验证如下：（k=1，m=2）
①first和helper移动0次，现在first指向第1个小孩，helper指向第5个小孩。 ②开始报数（1）first和helper同时移动1次，现在first指向第2个小孩，helper指向第1个小孩，first指向的第2个小孩出列。然后first指向第3个小孩，helper指向第1个小孩。现在链表中，有1、3、4、5。
（2）first和helper同时移动1次，现在first指向第4个小孩，helper指向第3个小孩，first指向的第4个小孩出列。然后first指向第5个小孩，helper指向第3个小孩。现在链表中，有1、3、5。
（3）first和helper同时移动1次，现在first指向第1个小孩，helper指向第5个小孩，first指向的第1个小孩出列。然后first指向第3个小孩，helper指向第5个小孩。现在链表中，有3、5。
（4）first和helper同时移动1次，现在first指向第5个小孩，helper指向第3个小孩，first指向的第5个小孩出列。然后first指向第3个小孩，helper指向第3个小孩。现在链表中，有3。
③因为first==helper，所以算法结束，最后一个出列的就是3。
完整代码
public class Josepfu { public static void main(String[] args) { // 测试构建环形链表和遍历是否正确 CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(); circleSingleLinkedList.addBoy(125);// 加入125个小孩节点 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 cur = null; // 辅助变量，帮助构建环形链表 // 使用for来创建环形链表 for (int i = 1; i <= nums; i++) { // 根据编号，创建小孩节点 Boy boy = new Boy(i); // 如果是第一个小孩 if (i == 1) { first = boy; first.setNext(first); // 构成环 cur = first; // 让cur指向第一个小孩 } else { cur.setNext(boy); boy.setNext(first); cur = boy; } } } // 遍历当前的环形链表 public void showBoy() { // 判断链表是否为空 if (first == null) { System.out.println("没有任何小孩"); return; } // 因为first不能动，因此我们仍然使用一个辅助变量来完成遍历 Boy cur = first; while (true) { System.out.printf("小孩的编号 %d \n", cur.getNo()); if (cur.getNext() == first) { // 说明已经遍历完毕 break; } cur = cur.getNext(); // curBoy后移 } } // 根据用户的输入，计算出小孩出圈的顺序 /** * startNo 表示从第几个小孩开始数数 * countNum 表示数几下 * 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) { // 说明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; }} 转载地址：http://payki.baihongyu.com/
你可能感兴趣的文章
c语言swap(a,b)值交换的4种实现方法
查看>>
C++中class类 的 构造函数、析构函数
查看>>
C++小知识点
查看>>
【转载】zedboard中PL_GPIO控制（8个sw、8个leds）
查看>>
zedboard烧写程序到FLASH，用于QSPI Flash启动
查看>>
软件工程师，你必须知道的20个常识
查看>>
常用STL算法2_查找
查看>>
常用STL算法3_排序
查看>>
常用STL算法4_拷贝和替换
查看>>
STL综合案例
查看>>
01背包问题
查看>>
O(logn)时间复杂度求Fibonacci数列
查看>>
【转】腾讯十年运维老兵：运维团队的五个“杀手锏”
查看>>
Iterator_traits
查看>>
Zedboard中的SPI通信记录文档（已实现）
查看>>
Android 发布到google Play的app搜索不到问题的解决
查看>>
Flutter 网络请求之基于dio的简单封装
查看>>
Flutter UI基础 - 路由之Navigator详解
查看>>
Flutter UI基础 - Widgets 之 InkWell 和 Ink
查看>>
Spring - sentinel和hystrix比较
查看>>