单向环形链表与约瑟夫问题

• 单向环形链表与约瑟夫问题
  • 基本介绍
  • 实现思路
    • 约瑟夫问题
    • 构建单向环形链表
    • 遍历环形链表
    • 出圈
  • 代码实现

基本介绍

Josephu问题为：设编号为 1，2，…n 的 n 个人围坐一圈，约定编号为k (1<=k<=n)的人从1开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

实现思路

约瑟夫问题

用一个不带头结点的循环链表来处理Josephu问题：先构成一个有 n 个结点的单循环链表然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。

构建单向环形链表

1. 先创建第一个节点，让first指向该节点，并形成环形
2. 后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可。

遍历环形链表

1. 先让一个辅助指针(变量)cur，指向first节点
2. 然后通过一个while循环遍历该环形链表即可，当cur.next == first结束

出圈

1. 定义一个辅助节点helper，最终目的是让它指向待出圈节点的前一个结点
2. 首先遍历使helper指向first节点的前一个节点，也就是环形链表的“尾部”
3. 根据起点序号k，让first指向起点前一个结点，即移动k-1次
4. 循环移动m-1次，每次数到 m 输出help.next的值，并判断help.next == helper,即判断是否还有一个节点，是则退出循环，否则使helper.next == helper.next.next，即使help.next置空

代码实现

public class Josephu {
    public static void main(String[] args) {
        CircleSingleLinkedList list = new CircleSingleLinkedList();
        list.add(9);
        list.list();
        list.getOrder(3, 3, 9);
    }
}

// 环形单向链表
class CircleSingleLinkedList {

    // 创建一个first节点，当前没有编号
    private CircleNode first = new CircleNode(-1);

    // 添加nums个节点
    public void add(int nums) {
        // 对 nums 进行数据校验
        if (nums < 1) {
            System.out.println("nums不合法");
            return;
        }
        // 创建辅助指针cur
        CircleNode cur = null;
        // 使用for循环创建环形链表
        for (int i = 1; i <= nums; i++) {
            // 根据编号创建节点
            CircleNode circleNode = new CircleNode(i);
            if (i == 1) {
                first = circleNode;
                circleNode.next = circleNode;
            } else {
                cur.next = circleNode;
                circleNode.next = first;
            }
            cur = circleNode;
        }
    }

    // 遍历输出链表
    public void list() {
        if (first == null) {
            System.out.println("链表为空");
            return;
        }
        CircleNode cur = first;
        while (true) {
            System.out.println(cur.getNum());
            if (cur.next == first) {
                break;
            }
            cur = cur.next;
        }
    }
    
    /** 输出出圈顺序
     * @param start 起点
     * @param count 每次数的节点个数
     * @param nums  初始节点数量
     */
    public void getOrder(int start, int count, int nums) {
        // 数据校验
        if (first == null || start < 1 || start > nums) {
            System.out.println("参数输入有误");
            return;
        }
        // 创建一个辅助指针
        CircleNode helper = first;
        // 使用 while循环让 helper指向最后一个节点
        while (helper.next != first) {
            helper = helper.next;
        }
        // 定位起点，移动helper到起点前面的节点、
        for (int i = 0; i < start - 1; i++) {
            helper = helper.next;
        }
        while (true) {
            // 开始数数
            for (int i = 0; i < count - 1; i++) {
                helper = helper.next;
            }
            System.out.print(helper.next.getNum() + " ");
            // 圈中只有一个节点时退出循环
            if (helper.next == helper.next.next) {
                break;
            }
            helper.next = helper.next.next;
        }
    }
}

// 环形单向链表的节点
class CircleNode {
    private int num; // 编号
    public CircleNode next; // 指向下一个节点，默认null

    public CircleNode(int num) {
        this.num = num;
    }

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }
}