[置顶] java循环链表实现约瑟夫环问题

说明：测试程序，输入一个数字构成约瑟夫环，再输入另外一个数字来以此数数。最后剩下的那个人为生存者，或者猴子大王。

学习笔记：1 约瑟夫环在删除过程中要动态改变current以及prior的值。

<pre name="code" class="java">package com.marthevin.linkedlist;

import java.util.Scanner;

public class YuesefuCircleTest {

/**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
   System.out.println("Input a num to create a circle....");
           Scanner  scanner = new Scanner(System.in);
           int N = scanner.nextInt();
           System.out.println("Input a num to count...");
           int M = scanner.nextInt();
           int[] array = new int[N];
           for(int i=1;i<=N;i++)
           {
           array[i-1] =i;
           }

          YuesefuCircle circle = new YuesefuCircle();
          circle.createCircleByArr(array);
          circle.deleteNodeByDivident(M);
          circle.printCircle();

}

}
class NodeC{
NodeC next;
int data;
public NodeC(int data)
{
this.data = data;
this.next = null;
}
}

class YuesefuCircle{
NodeC head,tail;
int count = 0;  //count控制最终的循环是否继续
int divident = 0; //表示输入几个数之后删除节点

public NodeC deleteNodeByDivident(int div)
{
this.divident = div;
NodeC current = head, prior = head;
while(this.count>1)
{
for(int i=1;i<div;i++)
{
prior = current;
current = current.next;
}
//删除current
if(current==head) //current 为 head 删除head  
{
head = head.next;
current = head;
}else if(current==tail) //current为tail 删除tail 
{
tail = prior;
tail.next = head;
current = head;
}else{
prior.next = current.next;
current = prior.next;
}
count--;
}
return head;
}

public int createCircleByArr(int[] arr)
{
int number = 0;
int length = arr.length;
for(int i=1;i<=length;i++)
{
NodeC newnode = new NodeC(arr[i-1]);
if(i == 1)
{
head = newnode;
tail = newnode;
}else{
tail.next = newnode;
tail = newnode;
newnode.next = head;
}
number++;
count++;
}
return number;
}

public void printCircle()
{
if(head==null)
{
System.out.println("null list...");
}
System.out.println("count= "+count+"\r\n"+"person left= "+head.data);
}

public YuesefuCircle()
{
head = tail = null;
}



}