Java 单向环形链表 Java用单向环形链表来解决约瑟夫环Josepfu问题
叶绿体不忘呼吸 人气:0想了解Java用单向环形链表来解决约瑟夫环Josepfu问题的相关内容吗,叶绿体不忘呼吸在本文为您仔细讲解Java 单向环形链表 的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Java,单向环形链表,Java,约瑟夫环,Java,Josepfu,下面大家一起来学习吧。
简单介绍
如果把单链表的最后一个节点的指针指向链表头部,而不是指向NULL,那么就构成了一个单向循环链表,通俗讲就是让尾节点指向头结点。
单向环形链表应用场景:Josephu(约瑟夫、约瑟夫环)问题:
设编号为1, 2, … n的n个人围坐一圈,约定编号为k (1<=k<=n)的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。
代码实现
节点类
//节点类 class JNode { private int id; private JNode next; public JNode(int id) { this.id = id; } public int getId() { return id; } public JNode getNext() { return next; } public void setNext(JNode next) { this.next = next; } }
链表类(包括节点管理和约瑟夫环问题解决)
//链表类 class CircleSingleLinkedList { private JNode first = null; //定义第一个节点,未创建时为null //添加节点,构建环形链表 public void add(int num) { if (num < 1){ System.out.println("创建个数不符合规定!"); return; } JNode curNode = null; //辅助变量 for (int i = 1; i <= num; i++) { JNode newNode = new JNode(i); if (i == 1){ //第一个节点较为特殊 first = newNode; //真正创建了第一个节点 first.setNext(first); //形成环状 curNode = first; //让辅助变量开始作用 }else { //第二个及其之后节点 curNode.setNext(newNode); //让当前节点指向新建的节点 newNode.setNext(first); //让新建的节点指向第一个节点,形成环状 curNode = newNode; //更新辅助变量 } } } //遍历链表 public void list(){ if (first == null){ System.out.println("链表为空!"); return; } JNode temp = first; while (true){ System.out.printf("取出节点%d\n",temp.getId()); if (temp.getNext() == first){ //说明已经遍历到最后一个了 break; } temp = temp.getNext(); } } //根据参数让节点出圈(Josepfu) public void josepfu(int startNode,int count,int num){ //startNode为开始的那个节点,count为每次数第几个,num为链表节点个数 if (first == null || startNode < 1 || count < 1 || startNode > num){ System.out.println("链表为空或者输入的参数不符合标准!"); return; } //让first移动到startNode指定的节点,即移动startNode-1次 for (int i = 0; i < startNode - 1; i++) { first = first.getNext(); } //创建一个辅助变量,让其指向最后一个节点(first前一个) JNode helper = first; while (helper.getNext() != first){ helper = helper.getNext(); } //开始按照要求出圈,每次都让helper和first移动count-1次 while (true){ if (helper == first){ //圈中只剩下一个节点 break; } for (int i = 0; i < count - 1; i++) { first = first.getNext(); helper = helper.getNext(); } //此时first指向的即为要出圈的节点 System.out.printf("节点%d出圈\n",first.getId()); //将出圈的节点从链表中移除 first = first.getNext(); helper.setNext(first); } System.out.printf("节点%d为最后一个节点",first.getId()); } }
测试类
/** * @Author: Yeman * @Date: 2021-10-15-22:33 * @Description: */ public class JosepfuTest { public static void main(String[] args) { CircleSingleLinkedList linkedList = new CircleSingleLinkedList(); linkedList.add(5); linkedList.list(); System.out.println("==================="); linkedList.josepfu(1,2,5); } }
加载全部内容