【Java数据结构】Java环形链表实现约瑟夫(Josephus)问题

约瑟夫问题

约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）详见百度百科。

“丢手绢”游戏模拟约瑟夫问题

这里用小孩子们玩的“丢手绢”游戏来说明和演示约瑟夫问题：n个小孩围成一圈，从第k个小孩开始从1报数，数到m的小孩时将手绢丢给他，拿到手绢的小孩自动出列，然后再让出列的小孩的下一个小孩开始从1报数，数到m的小孩，将手绢丢给他，这个小孩自动出列，以此类推，直到最后剩下的一个小孩成为赢家。例如k = 4，n=6，m=2，出列的顺序是：5，1，3，6，4，剩下的小孩为2。
分析：
（1）将小孩子们组成的圈作为一个环形链表；
（2）小孩出列的动作看作是从链表中删掉一个节点；
（3）模拟出列过程，直到链表中剩下一个节点为止。

小孩节点实体类

package com.jpc.linkedlist.four;

public class Boy {
	
	private int id;
	private Boy next;
	
	public Boy(int id) {
		this.id = id;
	}

	//此处省略get/set方法

	@Override
	public String toString() {
		return "小孩编号 " + this.getId();
	}
	
}

环形链表

环形链表即首尾相连的链表，最后一个节点的next域指向第一个节点，该链表可以是单向链表也可以是双向链表，由于其基本思路大体一致，这里以单向环形链表来说明。

增：环形链表添加数据(按添加顺序存储)

1、如果是第一个节点，就将该节点赋值给first变量(用于表示第一个添加进链表的节点数据)，并且将first赋值给first自身的next变量；
2、定义一个变量temp指向链表的第一个节点first；
3、对于非首个节点，将该节点赋值给temp的next变量，并且将first节点的内存地址赋值给该节点的next变量，以形成首尾相连。

删：按照节点的编号删除

1、定义一个temp变量指向first节点；
2、定义一个标记flag用于标记是否找到了指定编号的节点；
3、用temp遍历链表节点，每次将temp指向下一个节点，直到找到temp.next.id与指定编号相同的节点或遍历结束没有找到，如果找到就将flag变为true；
4、如果flag为true，就判断temp.next是否与first相等，如果相等就表明要删除的节点是第一个，因此把temp.next.next赋值给first，然后将first赋值给temp的next变量，保证首尾相连；
5、如果temp.next与first不相等，就表明不是要删除第一个，那么此时只需要将temp.next.next赋值给temp.next即可；
6、为了解决约瑟夫问题，本例的删除方法将返回一个被删除节点的下一个节点数据，即temp.next。

改：可以参考上一篇博客或上上一篇博客

略

查：根据编号查找

1、定义一个temp变量指向first节点；
2、定义一个标记flag用于标记是否找到了指定编号的节点；
3、用temp遍历链表节点，每次将temp指向下一个节点，直到找到temp.next.id与指定编号相同的节点或遍历结束没有找到，如果找到就将flag变为true；
4、如果为true就返回temp.next。

查：遍历

1、定义一个temp变量指向first节点；
2、每次将temp输出后，将其指向下一个节点，如果下一个节点是first就结束遍历。

代码实现单向环形链表模拟“丢手绢”游戏(outList()：约瑟夫问题)

package com.jpc.linkedlist.four;

public class CircleSingleLinkedList {
	
	private Boy first;

	//一次性创建多个小孩节点，形成单向环形链表
	public void addBoys(int nums) {
		//校验用户输入数据的合法性
		if(nums < 1) {
			System.out.println("输入的数据'" + nums + "'非法");
			return;
		}
		Boy temp = null;
		for(int i = 1; i <= nums; i ++) {
			Boy boy = new Boy(i);
			if(i == 1) {
				first = boy;
				first.setNext(first);
				temp = first;
			} else {
				temp.setNext(boy);
				boy.setNext(first);
				temp = temp.getNext();
			}
		}
	}
	
	//遍历环形链表
	public void list() {
		if(first == null) {
			System.out.println("链表为空！");
			return;
		}
		Boy temp = first;
		while(true) {
			System.out.println(temp);
			if(temp.getNext() == first) {
				break;
			}
			temp = temp.getNext();
		}
	}
	
	//根据编号，查找对应Boy
	public Boy select(int id) {
		//校验用户输入数据的合法性
		if(id>length() || id<1) {
			System.out.println("输入的数据非法！");
			return null;
		}
		Boy boy = null;
		Boy temp = first;
		do{
			if(temp.getId() == id) {
				boy = temp;
				break;
			}
			temp = temp.getNext();
		}while(temp != first);
		return boy;
	}
	
	//查询节点个数
	public int length() {
		int sum = 0;
		Boy temp = first;
		if(temp==null) {
			System.out.println("链表为空！");
			return sum;
		}
		do{
			sum ++;
			temp = temp.getNext();
		}while(temp != first);
		return sum;
	}
	
	//根据用户输入，生成一个出队顺序（模拟约瑟夫问题的核心）
	public void outList(int startId, int step) {
		//校验用户输入数据的合法性
		if(startId>length() || startId<1 || step<1) {
			System.out.println("输入的数据非法！");
			return;
		}
		//从用户指定位置的小孩节点开始报数
		Boy temp = select(startId);
		int length = length();
		//循环节点长度-1次，最后要留下一个小孩作为胜利者存在
		for (int j = 1; j < length; j ++) {
			//开始报数，找到报数为指定step的小孩节点的上一个小孩节点temp
			for (int i = 1; i < step - 1; i++) {
				temp = temp.getNext();
			}
			//打印出将要出列的小孩节点
			System.out.println(temp.getNext());
			//将目标节点删除，并且返回目标节点的下一个节点
			temp = delete(temp.getNext().getId());
		}
		System.out.println("胜利的小孩为："+first);
	}
	
	//删除节点数据
	public Boy delete(int id) {
		Boy temp = this.first;
		boolean flag = false;
		//本例情况特殊，不存在找不到id的情况，因此这里不再考虑
		while(true) {
			if(temp.getNext().getId() == id) {
				flag = true;
				break;
			}
			temp = temp.getNext();
		}
		//如果找到了指定的小孩节点，要分情况处理
		if(flag) {
			if(temp.getNext() == first) {
				first = temp.getNext().getNext();
				temp.setNext(first);
			}else {
				temp.setNext(temp.getNext().getNext());				
			}
		}else {
			System.out.println("要删除的小孩" + id + "不存在！");
		}
		return temp.getNext();
	}
}

测试类：

package com.jpc.linkedlist.four;

public class Test {

	public static void main(String[] args) {
		
		CircleSingleLinkedList list = new CircleSingleLinkedList();
		list.addBoys(6);
		System.out.println("参加游戏的小孩有以下几个：");
		list.list();
		System.out.println("出列顺序与胜利者如下：");
		list.outList(4, 2);
	}
}

运行测试类结果如下：