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

package org.example.test;

import java.util.HashSet;
import java.util.Set;

public class YSFTest {

    public static void main(String[] args) {
        YSFTest test = new YSFTest();
        System.out.println(test.ysf(5, 2));
    }

    static class Node {
        int val;
        Node next;

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

    Node pre;

    // 用一个单链表形成环，并保存一个前节点，每次遍历删除一个节点，直到节点个数为1。
    public int ysf(int n, int m) {
        // write code here
        Node head = new Node(1);
        Node cur = head;
        for (int k = 2; k <= n; k++) {
            Node node = new Node(k);
            cur.next = node;
            cur = cur.next;
            if (k == n) {
                pre = node;
                cur.next = head;
                cur = head;
            }
        }
        int i = 1;
        Node next;
        while (head.next != null) {
            next = head.next;
            if (i == m) {
                pre.next = next;
                head = next;
                i = 1;
                if (pre == head) {
                    break;
                }
                continue;
            }
            pre = head;
            head = next;
            i++;
        }
        return head.val;
    }
}