环形单链表的约瑟夫问题【Java实现】

小半 • 2023年2月2日上午10:14 • 后端开发 • 阅读 245

题目：

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

输入：

一个环形的单向链表的头节点 head 和报数的值 m。

最后生存下来的节点，且这个而节点自己组成环形单向链表，其他节点都删掉。

图示：

报 3 自杀

思路：

（1）找到头节点的前一个节点 last

（2）初始化一个计数变量 count

（3）一直循环，直到就剩一个节点为止，也就是last指针和head指针指向同一个节点的时候。

count=1，head和last指针向后移动，count=2,head和last指针向后移动，count=3，让last节点的next指针指向head节点的next（相当于删掉了当前head指针所指向的节点）。然后count归零。head再向下走一步。继续上面的过程。

代码实现：

    public static Node josephusKill(Node head, int m) {
        if (head == null || head.next == null || m < 1) {
            return head;
        }
        Node last = head;
        //让last成为头节点的上一个节点
        while (last.next != head) {
            last = last.next;
        }
        int count = 0;
        while (head != last) {
            ++count;
            if (count == m) {
                last.next = head.next;
                count = 0;
            } else {
                last = last.next;
            }
            head = head.next;
        }
        return head;
    }

测试代码：

    public static void main(String[] args) {
        Node head1 = new Node(1);
        Node node1 = new Node(2);
        Node node2 = new Node(3);
        Node node3 = new Node(4);
        Node node4 = new Node(5);
        Node node5 = new Node(6);
        Node node6 = new Node(7);
        Node node7 = new Node(8);

        head1.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = head1;

        Node node = josephusKill(head1, 3);
        System.out.println("最后剩下的节点值："+node.value);

测试结果：

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/87969.html

环形单链表的约瑟夫问题【Java实现】

相关推荐