-
基本介绍
- 单向循环链表和单向链表基本一样，尾节点的next指向第一个节点
- 当链表中只有一个节点时，该节点的next指向本身
-
约瑟夫问题
- 基本介绍
- 设编号为 1，2，… n 的n个人围坐一圈，约定编号为 k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列
- 例如：编号为1,2,3,4,5 从1开始，数2次，则出队编号为2,1,5,3
- 实现思路
- 采用单向环形链表，将数到那个节点在环形链表中删除后，重新构建环形链表，直到剩下最后一个节点
- 由于采用的单向链表，所以需要两个指针，current指向当前的节点（也就是要出队的节点，初始值为head节点），currentBefore指向当前节点的前一个节点（用来删除当前节点，初始值为head节点的前一个节点）
- 将两个节点同时移动k-1次，第一次的报号位置，由于本身也要报号，所以k-1次（两个指针必须相连，且current在后）
- 开始报号，将两个节点同时移动k-1次（原理同上）
- 出队current = current.next; currentBefore = current;
- 当current == currentBefore; 队列中就只剩下了一个节点（结束）
-
代码实现
-
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 +
'}';
}
}
（编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
