回顾数据结构（Java版）——循环单链表实现约瑟夫环

悠悠 2023-06-06 03:52 5阅读 0赞

> 约瑟夫环  
> 问题简述：自定义定义n个人，自定义m，谁数到m谁出列，最后剩下的一个是赢家。当然这道题的解法和变体很多，一些变体和这个的思想是一样的。

我认为值得注意的就是在删除节点时需要先获取头（head）的前驱指针（rear），必须借助这个前置指针才能进行简单有效的删除，当然方法也不止是前驱指针法

package com.wrial.singlelcircleinkedlist;
    /*
     * @Author  Wrial
     * @Date Created in 20:57 2019/10/9
     * @Description 单向环形链表实现约瑟夫环问题
     */
    
    public class Josephus {
    
    
        public static void main(String[] args) {
            SingleCircleLinkedList singleCircleLinkedList = new SingleCircleLinkedList();
            singleCircleLinkedList.add(10);
            singleCircleLinkedList.showAll();
            System.out.println(singleCircleLinkedList.playByOneStep(2));
            singleCircleLinkedList.showAll();
            singleCircleLinkedList.playAll(3);
    
        }
    }
    
    class SingleCircleLinkedList {
        SingleCircleLinkedList() {
    
        }
    
        private Node head = null;//头指针
    
        public void add(int num) {
            if (num < 1) {
                System.out.println("输入的总数不能小于1");
                return;
            }
            Node current = null;
            for (int i = 1; i <= num; i++) {
                //第一个节点的创建是特别的，需要加头指针和current指针
                if (i == 1) {
                    Node node = new Node(i);
                    head = node;
                    current = node;
                    node.next = node;
                } else {
                    Node node = new Node(i);
                    current.next = node;
                    node.next = head;
                    current = node;
                }
            }
        }
    
        public void showAll() {
            Node temp = head;
            if (temp == null) {
                System.out.println("空的循环链表");
                return;
            }
            while (true) {
                System.out.printf("id=%d\t", temp.getId());
                if (temp.next == head) {
                    System.out.println("遍历结束");
                    break;
                }
                temp = temp.next;
            }
        }
    
        public int playByOneStep(int m) {
            System.out.printf("游戏开始,从第一个开始，数到%d就踢出",m);
            //1.先找到head的前一个指针作为辅助指针，不然如果数字是1的话，没法删除当前节点
            Node rear = head;
            while (true) {
                if (rear.next == head) {
                    System.out.println(rear.getId());
                    break;
                }
                rear = rear.next;
            }
            //2.找到辅助指针后，然后按照规则删除并和head同时移动
    
            //3.如果m=1的话，那就是本身
            if (m > 1) {
                for (int i = 0; i < m - 1; i++) {
                    head = head.next;
                    rear = rear.next;
                }
            }
            int value = rear.next.getId();
            rear.next = rear.next.next;
            head = rear.next;
            return value;
        }
    
        public void playAll(int m) {
    
            while (true) {
                if (head.next == head){
                    System.out.println("赢家是"+head.getId());
                    System.out.println("游戏结束！");
                    break;
                }
                System.out.println("出列"+playByOneStep(m));
            }
        }
    
    
    }
    
    
    class Node {
    
        Node(int id) {
            this.id = id;
        }
    
        private int id;
        Node next;
    
        public int getId() {
            return id;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "id=" + id +
                    '}';
        }
    }