约瑟夫(环形链表)
/**
* @author 缪广亮
* @version 1.0
*/
class Joseph {
public static void main(String[] args) {
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5);
circleSingleLinkedList.list();
}
}
//Boy的节点类
class Boy {
public int no;//编号
public Boy next;
public Boy(int no){
this.no=no;
this.next=null;
}
@Override
public String toString() {
return "Boy{" +
"no=" + no +
'}';
}
}
//创建一个环形的单向链表
class CircleSingleLinkedList{
// 创建一个first结点，当前没有编号
private Boy first=new Boy(-1);
// 添加小孩结点，构建成一个环形链表
public void addBoy(int nums){
// nums校验
if (nums<1){
System.out.println("nums不能小于1~~~");
return;
}
Boy curBoy=null;//辅助指针，帮助构建环形链表
// 使用for来创建我们的环形链表
for (int i = 1; i <=nums ; i++) {
// 根据编号创建小孩节点
Boy boy = new Boy(i);
// 如果是第一个小孩
if (i==1){
first=boy;
first.next=first;//构成一个环
curBoy=first;//让curBoy指向第一个小孩
}else {
curBoy.next=boy;//
boy.next=first;//
curBoy=boy;
}
}
}
// 遍历环形链表
public void list(){
if (first==null){
System.out.println("环形链表为空,无小孩");
return;
}
// first不能动，所以需要一个辅助指针完成遍历
Boy curBoy=first;
while (true){
System.out.printf("小孩的编号%d \n",curBoy.no);
if (curBoy.next==first)//遍历完成
break;
curBoy=curBoy.next;
}
}
}