Java 约瑟夫环问题：面向对象与链表实现详解

以下是用面向对象和链表实现约瑟夫环问题的 Java 代码示例：

使用面向对象实现：

public class JosephusCircle {
    private Node head;
    private int size;

    private class Node {
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    public JosephusCircle(int size) {
        this.size = size;
        buildCircle();
    }

    private void buildCircle() {
        head = new Node(1);
        Node current = head;
        for (int i = 2; i <= size; i++) {
            current.next = new Node(i);
            current = current.next;
        }
        current.next = head;
    }

    public void eliminate(int m) {
        Node prev = head;
        while (size > 1) {
            for (int i = 0; i < m - 1; i++) {
                prev = prev.next;
            }
            prev.next = prev.next.next;
            size--;
        }
        head = prev;
    }

    public int getSurvivor() {
        return head.data;
    }

    public static void main(String[] args) {
        int size = 7;
        int m = 3;
        JosephusCircle circle = new JosephusCircle(size);
        circle.eliminate(m);
        System.out.println('Survivor: ' + circle.getSurvivor());
    }
}

使用链表实现：

import java.util.LinkedList;

public class JosephusCircle {
    public static int getSurvivor(int n, int m) {
        LinkedList<Integer> circle = new LinkedList<>();

        // 构建初始环
        for (int i = 1; i <= n; i++) {
            circle.add(i);
        }

        int index = 0;
        while (circle.size() > 1) {
            index = (index + m - 1) % circle.size();
            circle.remove(index);
        }

        return circle.getFirst();
    }

    public static void main(String[] args) {
        int n = 7;
        int m = 3;
        int survivor = getSurvivor(n, m);
        System.out.println('Survivor: ' + survivor);
    }
}

以上两种实现方式都可以解决约瑟夫环问题，只是采用了不同的数据结构和算法。