解决约瑟夫环

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后 [1] 结果+1即为原问题的解。

首先定义一个环形链表，先初始化n个人，用for语句，形成环形链表，定义一个head，cur，boy（待插入的），从1开始，游戏就是1开始。如果j=1，就新建boy把boy当head，然后cur.next=cur自身形成环形。不是，就把cur.next=boy,boy.next=head,cur=boy,形成环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ListNode first=null;
     ListNode help=null;//解决约瑟夫问题的节点
     ListNode cur=null;
     for (int i = 1; i <=n; i++) {
         if (i==1){
             ListNode boy=new ListNode(i);
             first=boy;
             cur=boy;
             cur.next=first;



         }else{
             ListNode boy=new ListNode(i);
             cur.next=boy;
             boy.next=first;
             cur=boy;
         }
     }

解决思路，通过便利，使help在head的前一个，就是help.next=head,如果要改变开始顺序，就把head，help移动k-1次，从k开始

1
2
3
4
5
6
7
8
9
help=first;
      while (help.next!=first){
          help=help.next;
      }
      //初始化，在最初规定的位置
      for (int i = 0; i < start- 1; i++) {
          first=first.next;
          help=help.next;
      }

解决方法，当head！=help（不都为空)才成立，和初始化差不多，移动m-1，head=head.next，help。next=head，最终跳出循环，方法结束。

1
2
3
4
5
6
7
8
9
10
11
12
while (first!=help) {
            for (int i = 0; i < m - 1; i++) {
                first=first.next;
                help=help.next;

            }
            System.out.println(first.val);
            first=first.next;
            help.next=first;
        }
        System.out.print(first.val+" ");
    }

最终完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public static void josephu(int start,int m,int n){
        ListNode first=null;
        ListNode help=null;
        ListNode cur=null;
        for (int i = 1; i <=n; i++) {
            if (i==1){
                ListNode boy=new ListNode(i);
                first=boy;
                cur=boy;
                cur.next=first;



            }else{
                ListNode boy=new ListNode(i);
                cur.next=boy;
                boy.next=first;
                cur=boy;
            }
        }
        help=first;
        while (help.next!=first){
            help=help.next;
        }
        //初始化，在最初规定的位置
        for (int i = 0; i < start- 1; i++) {
            first=first.next;
            help=help.next;
        }
        while (first!=help) {
            for (int i = 0; i < m - 1; i++) {
                first=first.next;
                help=help.next;

            }
            System.out.println(first.val);
            first=first.next;
            help.next=first;
        }
        System.out.print(first.val+" ");
    }