基本介绍
约瑟夫问题
代码实现
public class CircleSingleLinkedListDemo { public static void main(String[] args) { CircleSingleLinkedLis circleSingleLinkedLis = new CircleSingleLinkedLis(); // 创建并显示单向环形链表 circleSingleLinkedLis.create(10); circleSingleLinkedLis.show(); // 实现约瑟夫问题 System.out.println("---约瑟夫问题---"); circleSingleLinkedLis.josephu(5, 10, circleSingleLinkedLis.size()); } } // 单向环形链表类 class CircleSingleLinkedLis { private Children head; // 头节点,将加入的第一个节点作为头节点(不能动,在约瑟夫环中可以动) // 创建单向环形链表(参数为有几个节点) public void create(int number) { if (number < 2) { System.out.println("至少两个节点"); return; } Children current = null; // 尾指针 指向下一个节点为头节点的节点(方便插入,不需要每次都遍历) for (int i = 1; i <= number; i++) { // i作为节点的编号 Children children = new Children(i); if (null == head) { // 第一个节点 自己指向自己 单独处理也是为了防止空指针 head = children; children.next = head; current = head; } else { // 先将当前节点的下一个节点指向要添加的节点,再后移当前节点,再将当前节点的下一个节点指向头节点 current.next = children; current = current.next; children.next = head; } } } // 显示单向环形链表 public void show() { if (null == head) { System.out.println("单向环形链表为空"); } Children temp = head; while (null != head) { System.out.println(temp); temp = temp.next; // 后移节点 if (temp == head) { break; // 到头节点了 退出 } } } // 获取链表节点个数 public int size() { int sum = 0; Children temp = head; while (null != temp ) { sum++; temp = temp.next; if (temp == head) { break; } } return sum; } /** * 约瑟夫问题实现(一群小孩围在一起,由第k个小孩报n下数,停止报数的那个小孩出圈,问小孩出圈的顺序) * 采用两个指针(一个指向当前报数的孩子,另一个指向报数孩子的前一个孩子,因为单链表删除必须拿到当前节点的前一个节点) * @param start 开始报数的节点 * @param count 报多少下 * @param size 总共有多少个小孩(此处不能链表的有效个数) */ public void josephu(int start, int count, int size) { if (null == head || start < 1 || start > size || size > this.size()) { System.out.println("输入的数据不合法"); return; } Children current = head; // 当前节点 Children currentBefore = current; // 当前节点的前一个节点 while (currentBefore.next != head) { // 寻找当前节点的前一个节点 currentBefore = currentBefore.next; // 指针后移 } for (int i = 0; i < start - 1; i++) { // 将两个指针移动到起始位置 例 1 -> 3 需移动2次 则是 start - 1 current = current.next; currentBefore = currentBefore.next; } while (current != currentBefore) { // 如果圈中只剩一个小孩 则两个指针重合 // 从起始位置报数 由于起始节点本身也要报数 则是移动 count - 1 for (int i = 0; i < count - 1; i++) { current = current.next; currentBefore = currentBefore.next; } // 报数完毕 移除当前节点 并重新构建链表 System.out.println(current); current = current.next; // 后移当前指针 currentBefore.next = current; // 重新构建链表 } System.out.println(current); // 输出圈中最后一个节点的信息 } } // 链表节点类 class Children { public int no; public Children next; // 指向下一个节点 public Children(int no) { this.no = no; } @Override public String toString() { return "Children{" + "no=" + no + ‘}‘; } }
原文:https://www.cnblogs.com/xiaokantianse/p/13579573.html