约瑟夫环问题

public class Solution {
    //约瑟夫环问题
    public int LastRemaining_Solution(int n, int m) {
        if(n<1||m<1)
           return -1;
        if(n==1)
            return 0;
        Node head=new Node(0);
        Node tmp=head;
        for(int i=1;i!=n;i++)
        {
              Node node=new Node(i);
              tmp.next=node;
              tmp=node;
        }
        tmp.next=head;//构建约瑟夫环
        //printLink(head);
        while(head.next!=null&&head.next!=head)
        {
             for(int i=1;i!=m-1;i++)
             {
                  head=head.next;

             }
             Node tmp2=head.next;
             head.next=tmp2.next;
             tmp2.next=null;
             head=head.next;

        }

        return head.value;
    }
    static class Node{

        public int value;
        Node next;

        public Node(int v){
             this.value=v;
        }
    }


    //方法二 递推公式法
     public int LastRemaining_Solution2(int n, int m) {
          if(n==0)
             return -1;
          if(n==1)
             return 0;
          else 
            return(LastRemaining_Solution2(n-1,m)+m)%n;
     }


    //打印循环链表
    public void printLink(Node head)
    {
         Node tmp=head;
         System.out.print(tmp.value+" ");
         head=head.next;
         while(head!=tmp)
         {
             System.out.print(head.value+" ");
             head=head.next;

         }
    }
    public static void main(String[]args){
        //System.out.println("Hello");
        Solution s=new Solution();

        System.out.println(s.LastRemaining_Solution2(6,7));

    }
}