题解 | #环形链表的约瑟夫问题#

import java.util.*;

// 思路：在本题的众多解法中，我们选择的是使用链表的方法。通过构建一个双向的环形链表，每一次淘汰一名玩家，最终剩下的那一名玩家就是获胜者。
public class Solution {

    // 定义一个类(双向环形链表)
    public class ListNode {
        public int val; // 节点的值
        public ListNode next; // 当前节点指向的下一个节点
        public ListNode pre; // 当前节点指向的上一个节点
        public ListNode(int val) { // 构造函数
            this.val = val;
        }
    }

    /**javascript:void(0);
     *
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    public int ysf (int n, int m) {
        // write code here

        // 一些特殊情况的处理
        if (1 == n) { // 如果只有一个人参与游戏，直接返回 1 即可
            return 1;
        }
        if (1 == m) { // 如果报到的数字 m 为 1 时，直接返回 n - 1
            return n - 1;
        }

        // 具体代码实现
        ListNode head = new ListNode(1); // 初始化一个头节点
        head.next = null;
        head.pre = null;

        ListNode tmpNode = head; // 定义一个辅助节点

        for (int i = 2; i <= n; i++) {

            ListNode newNode = new ListNode(i); // 创建一个新的节点
            newNode.next = null;
            newNode.pre = tmpNode;

            tmpNode.next = newNode;

            tmpNode = newNode;
        }
        // 形成一个环形结构
        tmpNode.next = head;
        head.pre = tmpNode;

        tmpNode = head;

        int account =
            0; // 定义一个计数器(当计数器中存放的数等于 m 值时，淘汰该名玩家)
        int num = n; // 游戏一开始一共有 n 个玩家

        while (num != 1) { // 当只剩下一名玩家时，游戏结束
            account++; // 玩家报数
            if (account == m) {

                ListNode preNode = tmpNode.pre;
                ListNode nextNode = tmpNode.next;

                preNode.next = nextNode;
                nextNode.pre = preNode;

                tmpNode = nextNode;
                num--; // 淘汰一名玩家
                account = 0; // 同时计数器要重新归为 0
            } else {
                tmpNode = tmpNode.next;
            }
        }
        return tmpNode.val;
    }
}