约瑟夫环java链表

以下是使用Java链表实现约瑟夫环的示例代码：

import java.util.LinkedList;

public class JosephusCircle {
    public static void main(String[] args) {
        int n = 7; // 总人数
        int k = 3; // 从第k个人开始报数
        int m = 4; // 报到m的人出列

        LinkedList<Integer> circle = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            circle.add(i);
        }

        int count = k - 1; // 从第k个人开始报数，所以初始计数器为k-1
        while (circle.size() > 1) {
            count = (count + m - 1) % circle.size(); // 计算出列的人在链表中的索引
            circle.remove(count); // 将出列的人从链表中移除
        }

        System.out.println("最后留下的人的编号是：" + circle.get(0));
    }
}

相关问题

约瑟夫环问题链表实现java

约瑟夫环问题是一个经典的计算机科学问题，它涉及到在一个环形链表上，每个节点有一个整数值，按照一定的步长（如7），从第一个节点开始计数，每到指定步长就删除当前节点，并将下一个节点提升到链表头部。如果步长为1，那么问题就是找到链表中的最后一个节点。

在Java中，我们可以使用LinkedList和循环来实现这个过程。首先创建一个Node类作为链表的基本元素，然后定义一个方法`josephus(int step)`，输入步长，开始遍历链表：

class Node {
    int value;
    Node next;

    // 构造函数
    public Node(int val) {
        this.value = val;
        this.next = null;
    }
}

public class JosephusRing {
    private Node head;

    // 添加节点
    public void addNode(Node node) {
        if (head == null) {
            head = node;
        } else {
            node.next = head;
            head = node;
        }
    }

    // 约瑟夫环问题
    public Node josephus(int step) {
        if (head == null || step <= 0) return null; // 链表为空或步长无效

        Node slow = head, fast = head;
        for (int i = 0; i < step - 1; i++) {
            fast = fast.next; // 快指针前进step-1次
            if (fast == null) { // 如果快指针到了链表尾部，则回到头
                fast = head;
            }
        }

        while (fast != null) { // 当快指针非空时，进行删除操作
            slow = slow.next;
            fast = fast.next;
        }

        return slow; // 返回新的头节点
    }
}

在这个实现中，我们使用了两个指针，一个慢指针每次移动一步，另一个快指针初始时也是一步，但在达到指定步长后会跳过一个节点继续前进。当快指针到达链表尾部时，链表长度已经减少了一个步长，此时慢指针的位置就是新的起始点。

JAVA约瑟夫环问题链表代码

约瑟夫环问题是一个经典的计算机科学问题，涉及将一组人围成一圈，从某个人开始按顺序报数，每次跳过一个人，直到只剩下最后一个人为止。在Java中解决这个问题，我们可以使用链表来模拟环形结构，并通过迭代或递归的方式来找到最后剩下的那个人。

这里是一个简单的迭代解约瑟夫环问题的链表代码示例：

public class Node {
    int data;
    Node next;

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

public class JosephusRing {
    private Node head;
    private int step;

    public JosephusRing(int k) {
        this.step = k;
    }

    // 添加节点到环中
    public void insertNode(Node newNode) {
        if (head == null) {
            head = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
    }

    // 解决约瑟夫环问题
    public Node findLastMan Standing() {
        if (head == null || step <= 0) {
            return null;
        }
        Node slow = head;
        Node fast = head;
        for (int i = 1; fast != null && fast.next != null; i++) {
            fast = fast.next.next;
            if (i % step == 0) {
                slow = slow.next;
            }
        }
        return slow;
    }
}

// 使用示例
public static void main(String[] args) {
    JosephusRing josephus = new JosephusRing(3); // 设置步长为3
    // 插入节点...
    Node lastStanding = josephus.findLastManStanding();
    System.out.println("当步长为3时，最后站着的是节点值为 " + lastStanding.data);
}

在这个代码中，我们首先创建了一个`JosephusRing`类，它有一个头结点和步长变量。然后有`insertNode`方法用于添加节点，以及`findLastManStanding`方法用于计算在给定步长下谁会是最后一个站在圈子里的人。