06、数据结构与算法 - 基础:环形链表和 josepfu 问题解决

构建环形链表思路

  • 创建第一个节点,first 指向该节点,并形成环装
  • 每创建一个新的节点,将该节点加入到已有的环形链表中

遍历环形链表

  • 先让一个辅助指针指向 first 节点
  • 然后通过一个 while 循环遍历该环形链表知道 辅助指针的 next 下一个节点 == first 结束

Josepfu 问题

josepfu 问题为:设编号为 1,2,……n 个人围坐一圈,约定编号为 k(1 <= k <= n)的人从 1 开始报数,数到 m 的人出列,下一位又从 1 开始报数,数到 m 的人又出列,直到所有的人都出列为止

Josepfu 问题思路

使用一个不带头结点的循环链表来处理,首先构成一个有 n 个节点的单循环链表,然后由 k 节点起从 1 开始计数,计数到 m 时,对应节点从链表中删除,然后再从被删除节点的下一个节点又从 1 开始计数,知道所有节点都从链表中删除为止

  • 创建一个辅助指针 helper,指向环形链表的最后的节点,每次报数前 让 first 和 helper 移动k 开始节点 - 1 次
  • 报数时,让 first 和 helper 节点 同时移动 m 计数次数 - 1 次
  • 将 first 指向的节点出列,first = first.next helper = helper.next原来 first 节点失去引用回收

josepfu 问题代码实现

package com.sqdkk.linkedList;

public class Josepfu {
   
     
    public static void main(String[] args) {
   
     
        // 构建环形链表
        CircleSingleLinked circleSingleLinked = new CircleSingleLinked();
        circleSingleLinked.addNode(20);
        //        circleSingleLinked.list();
        System.out.println("开始出列");
        circleSingleLinked.countNode(1, 5, 5);
    }
}

// 创建环形单向链表
class CircleSingleLinked {
   
     
    private Node first; // 创建一个 first 节点

    // 添加节点,构建环形链表
    public void addNode(int nums) {
   
     
        if (nums < 1) {
   
      // 判断节点数量,链表是否为空
            System.out.println("number 的值应该大于 1");
            return;
        }
        Node curNode = null; // 辅助指针,帮助构建环形链表
        for (int i = 1; i <= nums; i++) {
   
     
            Node node = new Node(i); // 根据编号创建节点
            if (i == 1) {
   
      // 如果是第一个节点
                first = node; // 设置第一个节点
                first.setNext(first); // 形成环形链表
                curNode = first; // 当前 curNode 指向 first 节点
            } else {
   
     
                curNode.setNext(node); // 最后一个节点的下一个节点指向 node
                node.setNext(first); // node 的下一个节点指向 first 形成环状
                curNode = node; // curNode 指向 node 最后一个节点
            }
        }
    }

    // 遍历当前环形链表
    public void list(){
   
     
        if (first == null) {
   
     
            System.out.println("链表为空");
            return;
        }
        Node curNode = first;
        while (true) {
   
     
            System.out.printf("Node 节点编号为 %d\n", curNode.getNo());
            if (curNode.getNext() == first) {
   
      // 当前节点的 next 后一个节点为第一个节点的话
                break;
            }
            curNode = curNode.getNext(); // 当前节点指针后移
        }
    }

    /**
     *
     * josepfu 问题为:
     * 设编号为 1,2,……n 个人围坐一圈
     * 约定编号为 k(1 <= k <= n)的人从 1 开始报数,数到 m 的人出列
     * 下一位又从 1 开始报数,数到 m 的人又出列,直到所有的人都出列为止
     *
     * 根据输入计算出列顺序
     *
     * @param startNo   开始节点位置
     * @param countNum  表示数几下
     * @param nums      标识开始时有多少节点
     */
    public void countNode(int startNo, int countNum, int nums) {
   
     
        // 参数校验
        if (first == null) {
   
      // 判断链表是否为空
            System.out.println("链表为空");
            return;
        }
        if (startNo < 1 || startNo > nums) {
   
      // 开始位置要大于 1,并且开始位置要小于节点的总数量
            System.out.println("参数错误,请注意开始位置与节点总数量");
            return;
        }

        Node helper = first; // 创建辅助指针,帮助完成出列
        while (true) {
   
     
            // 如果 helper 下一个节点指向 first 节点,为最后一个节点
            if (helper.getNext() == first) {
   
     
                break;
            }
            helper = helper.getNext();
        }
        // 报数前,先让 first 和 helper 移动 startNo - 1 次
        for (int i = 0; i < startNo - 1; i++) {
   
     
            first = first.getNext();
            helper = helper.getNext();
        }
        // 报数时,first 和 helper 指针同时移动 countNum - 1 次,然后出列
        while (true) {
   
     
            if (helper == first) {
   
      // 圈中只有一个节点,退出循环
                break;
            }
            for (int i = 0; i < countNum - 1; i++) {
   
     
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.printf("节点 %d 出列\n", first.getNo());
            // first 节点指向的节点出列
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的节点为:%d\n", first.getNo());
    }

}

// 创建一个 Node 节点
class Node{
   
     
    private int no; // 编号
    private Node next; // 下一个节点

    public Node(int no) {
   
     
        this.no = no;
    }

    public int getNo() {
   
     
        return no;
    }

    public void setNo(int no) {
   
     
        this.no = no;
    }

    public Node getNext() {
   
     
        return next;
    }

    public void setNext(Node next) {
   
     
        this.next = next;
    }
}