找出游戏的获胜者（java）

问题描述：（约瑟夫环）

样例输入：


代码如下：使用链表模拟法

import java.util.Scanner;
public class FindTheWinner {
    //找出游戏的获胜者
    //1 <= k <= n <= 500
    class Node{
        int data;
        Node next;
        public Node(int data) {
            this.data = data;
        }
    }
    public int findTheWinner(int n, int k) {//利用循环列表来解决
      if (k==1) return n;
      Node first=new Node(1);
      Node p=first;
        for (int i = 2; i <=n ; i++) {
            p.next=new Node(i);
            p=p.next;
        }
        p.next=first;//首尾相连
        Node p1=first;
        Node pre=null;
        int cnt=1;
        while (p1!=pre){
            pre=p1;
            p1=p1.next;
            cnt++;
            if (cnt==k){
                pre.next=p1.next;//删除p1所指的节点
                cnt=1;
                p1=pre.next;//将p1指向下一个节点
            }
        }
        return p1.data;
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int k=scanner.nextInt();
        FindTheWinner findTheWinner=new FindTheWinner();
        System.out.println(findTheWinner.findTheWinner(n,k));
    }
}

运行结果如下：