//解决约瑟夫问题
public class YueSeFu{
//定义链表的节点
public static class Node{
public int value;
Node next;
public Node(int data)
{
this.value=data;
}
}
//解决约瑟夫问题
/**
head 环形链表的头结点
num 所报的数
*/
public static Node yueSeFu(Node head,int num)
{
if(head==null||num<=0||head.next==head)
{
return head;
}
//当报数为1时,一定为最后一个数
if(num==1)
{ Node p=head;
while(head.next!=p)
{ Node Q=head;
head=head.next;
Q=null; //删除链表的节点
}
return head;
}
int t=0; //记录链表所达到的位置
while(head.next!=head) //当不为最后一个节点
{
++t;
if(t==num-1) //删除每次所报节点数为num的节点
{
Node p=head.next;
head.next=head.next.next;
p=null;
t=0;
}
head=head.next;
}
return head;
}
/**
进阶: 当环形链表长度为N,在O(N)复杂度完成操作
*/
public static Node NyueSeFu(Node head,int num)
{
if(head==null||num<=0||head.next==head)
{
return head;
}
//当报数为1时,一定为最后一个数留下来
if(num==1)
{ Node p=head;
while(head.next!=p)
{ Node Q=head;
head=head.next;
Q=null; //删除链表的节点
}
return head;
}
int leng=1;
Node p=head;
while(p.next!=head)
{
++leng;
p=p.next;
}
leng=getLive(leng,num);
while(--leng!=0)
{
head=head.next;
}
//最后一个节点
head.next=head;
return head;
}
//获得新老约瑟夫节点的关系(NuM(i)与Num(i-1))
public static int getLive(int len,int num)
{
if(len==1)
{
return 1;
}
return (getLive(len-1,num)+num-1)%num+1;
}
public static void main(String []args)
{
//System.out.println("Hello");
//构造约瑟夫环(1->2->3->4->1)
Node node=new Node(1);
node.next=new Node(2);
node.next.next=new Node(3);
node.next.next.next=new Node(4);
node.next.next.next.next=node;
// Node mode=yueSeFu(node,1);
//System.out.println(mode.value);
Node tnode=NyueSeFu(node,2);
System.out.println(tnode.value);
}
}