[数据结构与算法] 找出游戏的获胜者（java）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 找出游戏的获胜者（java） -> 正文阅读

[数据结构与算法]找出游戏的获胜者（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));
    }
}