package 栈和队列;
/**
*
* 数到3的人出列 ，看最后能剩下谁
* @author wangmeng
*
*/
class Node {
public Object data;
public Node next;
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Node() {
super();
// TODO Auto-generated constructor stub
}
public Node(Object data, Node next) {
super();
this.data = data;
this.next = next;
}
}
public class 用java实现链表并解决约瑟夫环问题 {
public static void main(String[] args) {
Node node1 = new Node("1",null);
Node node2 = new Node("2",null);
Node node3 = new Node("3",null);
Node node4 = new Node("4",null);
Node node5 = new Node("5",null);
Node node6 = new Node("6",null);
Node node7 = new Node("7",null);
Node header = node1;
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = node7;
node7.next = node1;
检测(header);
}
private static void 检测(Node header) {
Node n = header;
Node lastOne ;//表示上一个节点
int count = 1 ;
System.out.print("依次出列的顺序为：");
while(n != n.next){//最后环中只剩下一个人，那肯定是它的下一个就是它本身 即 n=n.next
lastOne = n;
n = n.next;
count ++ ;
if(count == 3){//若数到3，出列
lastOne.next = n.next;//上一个的节点的下一个就是当前的下一个 即lastOne.next = n.next;
count = 0;//count清 0
System.out.print(n.data + " ");//打印出列的元素
}
}
System.out.println();
System.out.println("最后剩下的是:" + n.data);
}
}
运行结果：
依次出列的顺序为：3 6 2 7 5 1
最后剩下的是:4
