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

import java.util.*;

/**
 * NC132 环形链表的约瑟夫问题
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    public int ysf (int n, int m) {
        // return solution1(n, m);
        // return solution2(n, m);
        // return solution3(n, m);
        return solution4(n, m);
        // return solution5(n, m);
    }

    /**
     * 链表(自建)
     * @param n
     * @param m
     * @return
     */
    private int solution1(int n, int m){
        ListNode head = new ListNode(1);
        ListNode node,curr;
        curr = head;
        for(int i=2; i<=n; i++){
            node = new ListNode(i);
            curr.next = node;
            curr = curr.next;
        }
        curr.next = head;

        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        curr = dummyHead;
        ListNode del;
        for(int i=1; i<=n-1; i++){
            for(int j=1; j<m; j++){
                curr = curr.next;
            }
            del = curr.next;
            curr.next = del.next;
            del.next = null;
        }

        return curr.val;
    }

    /**
     * 链表(数组模拟)
     * @param n
     * @param m
     * @return
     */
    private int solution2(int n, int m){
        int[] next = new int[n+1];
        for(int i=1; i<=n; i++){
            next[i] = i+1;
        }
        next[n] = 1;

        int curr = 1;
        for(int i=1; i<=n-1; i++){
            for(int j=1; j<m-1; j++){
                curr = next[curr];
            }
            next[curr] = next[next[curr]];
            curr = next[curr];
        }

        return curr;
    }

    /**
     * 链表(LinkedList)
     * @param n
     * @param m
     * @return
     */
    private int solution3(int n, int m){
        LinkedList<Integer> list = new LinkedList<>();
        for(int i=1; i<=n; i++){
            list.add(i);
        }

        int delIdx = 0;
        for(int i=1; i<=n-1; i++){
            delIdx = (delIdx+m-1)%list.size();
            list.remove(delIdx);
        }

        return list.get(0);
    }

    /**
     * 迭代
     *
     * X -> 删除(离开)
     *
     * 当 n=5 m=2 时
     *                                                            lastIdx = (lastIdx+m)%i
     * level 5:     索引idx   0   1   2   3   4                    lastIdx=2 = (0+2)%5
     *              编号num   1   2   3   4   5
     * level 4:     索引idx       |   0   1   2   3                lastIdx=0 = (2+2)%4
     *              编号num       X   3   4   5   1
     * level 3:     索引idx               |   0   1   2            lastIdx=2 = (0+2)%3
     *              编号num               X   5   1   3
     * level 2:     索引idx                       |   0   1        lastIdx=0 = (0+2)%2
     *              编号num                       X   3   5
     * level 1:     索引idx                               |   0    lastIdx=0
     *              编号num                               X   3
     *
     * 从level 1到level 5, 最终留下节点(编号3)的索引(lastIdx)变化为: 0 -> 0 -> 2 -> 0 -> 2
     * lastIdx = (lastIdx+m)%i
     *
     * 最终留下节点的编号即为: lastIdx+1(索引加1)
     *
     * @param n
     * @param m
     * @return
     */
    private int solution4(int n, int m){
        // 最后留下节点索引 一定为0
        int lastIdx = 0;

        // i -> 环中节点个数
        for(int i=2; i<=n; i++){
            lastIdx = (lastIdx+m)%i;
        }

        return lastIdx+1;
    }

    /**
     * 递归
     * @param n
     * @param m
     * @return
     */
    private int solution5(int n, int m){
        return J(n, m)+1;
    }

    /**
     * Josephus Circle
     * @param n
     * @param m
     * @return lastIdx
     */
    private int J(int n, int m){
        if(n == 1){
            return 0;
        }

        return (J(n-1,m)+m)%n;
    }

    /**
     * 链表节点
     */
    private class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
    }
}