单向环形链表
单向环形链表
Josephu(约瑟夫)问题
Josephu问题为:设编号为1,2,3,…,n的n个人围坐在一全圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,以此类推,直到所有人出列为止,由此产生一个出队编号的序列
提示:用一个不带头节点的循环链表来处理Josephu问题:先构成一个有n个节点单循环链表,然后由k节点起从1开始计数,计到m时,对应节点从链表中删除,然后再从被删除的节点的下一个节点又从1开始计数,直到最后一个节点从链表中删除,算法结束
构建一个单向环形链表思路
- 先构建第一个节点,让first指向该节点,并形成环形
- 后面当我们每创建一个节点,就把该节点,加入到已有的环形链表中即可
遍历该环形链表
- 先让一个辅助指针(变量)curBoy,指向first节点
- 然后通过一个while循环遍历该环形链表即可,curBoy.next=first结束
出圈思路
- 需要创建一个辅助指针(变量)helper,事先应该指向环形链表的最后这个节点
- 补充:小孩报数前,先让first和helper移动k-1次
- 当小孩报数时,让first和helper指针同时移动m-1次
- 这时就可以将first指向的小孩节点出圈
- first=first.next
- helper.next=first
- 原来first指向的节点就没有任何引用,就会被回收
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134
| public class Josephu { public static void main(String[] args) { CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(); int nums = 25; circleSingleLinkedList.addBoy(nums); circleSingleLinkedList.showBoy();
circleSingleLinkedList.countBoy(8, 2, nums); } }
class CircleSingleLinkedList { private Boy first = null;
public void addBoy(int nums) { if (nums < 1) { System.out.println("nums的值不正确~~~"); return; } Boy curBoy = null; for (int i = 1; i <= nums; i++) { Boy boy = new Boy(i); if (i == 1) { first = boy; first.setNext(first); curBoy = first; } else { curBoy.setNext(boy); boy.setNext(first); curBoy = boy; } } }
public void showBoy() { if (first == null) { System.out.println("链表为空~~~"); return; } Boy curBoy = first; while (true) { System.out.printf("小孩的编号 %d\n", curBoy.getNo()); if (curBoy.getNext() == first) { break; } curBoy = curBoy.getNext(); } }
public void countBoy(int startNo, int countNum, int nums) { if (first == null || startNo < 1 || startNo > nums) { System.out.println("参数输入有误~~~"); return; } Boy helper = first; while (true) { if (helper.getNext() == first) { break; } helper = helper.getNext(); } for (int i = 0; i < startNo - 1; i++) { first = first.getNext(); helper = helper.getNext(); } while (true) { if (helper == first) { break; } for (int j = 0; j < countNum - 1; j++) { first = first.getNext(); helper = helper.getNext(); } System.out.printf("小孩%d出圈\n", first.getNo()); first = first.getNext(); helper.setNext(first); } System.out.printf("最后留在圈中的小孩编号%d \n", first.getNo()); } }
class Boy { private int no; private Boy next;
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; }
}
|