环形单链表的约瑟夫问题

//解决约瑟夫问题

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);

	}
      
}