线性表环形单链表的约瑟夫问题如何实现实现

题目描述

package day03;/** * @Author yqq * @Date 2022/05/06 17:36 * @Version 1.0 * 环形单链表的约瑟夫问题 */public class JosephTest { public static void main(String[] args) { //创建一个环形链表 Node lastNode = new Node(10); Node node9 = new Node(9,lastNode); Node node8 = new Node(8,node9); Node node7 = new Node(7,node8); Node node6 = new Node(6,node7); Node node5 = new Node(5,node6); Node node4 = new Node(4,node5); Node node3 = new Node(3,node4); Node node2 = new Node(2,node3); Node headNode = new Node(1,node2); lastNode.next = headNode; joseph(headNode,lastNode,10,2,3); } /** * 解决环形单链表的约瑟夫问题 * @param headNode 首节点 * @param lastNode 尾结点 * @param size 节点个数 * @param start 从编号为start的节点报数 * @param count 每次数几下 */ public static void joseph(Node headNode,Node lastNode,int size,int start,int count){ //处理不合法的情况 //处理headNode为null的情况 if (headNode == null) throw new NullPointerException("headNode is null:" + headNode); //处理start和count不合法的情况 if (start < 1 || start > size || count <1) throw new IllegalArgumentException("参数不合法"); //设置编号为start的节点开始报数，并且使用headNode指向该节点 //把headNode和lastNode往后移动start-1次 for (int i = 0; i < start - 1; i++) { headNode = headNode.next; lastNode = lastNode.next; } //定义一个循环，用于循环的执行报数操作 while (size != 0){//如果size等于0，则停止报数 //执行报数操作，也就是找到需要出圈的小孩，使用headNode节点指向需要出圈的节点 //把headNode和lastNode往后移动count-1次 for (int i = 0; i < count - 1; i++) { headNode = headNode.next; lastNode = lastNode.next; } //需要出圈的节点编号，也就输出headNode保存的数据值 System.out.print(headNode.data+"、"); //实现小孩的出圈操作，也就是把headNode从环形单链表中删除 //获得删除节点的后一个节点 Node nextNode = headNode.next; //设置lastNode的next为nextNode lastNode.next = nextNode; //设置headNode的next值为null headNode.next = null; //更新size的值 size --; //设置headNode指向nextNode headNode = nextNode; } } /** * 节点类 */ private static class Node{ /** * 用于保存节点中的数值 */ private Object data; /** * 用于保存下一个节点的地址值 */ private Node next; /** * 专门为data做初始化的工作 * @param data */ public Node(Object data) { this.data = data; } /** * 专门为data和next做初始化的工作 * @param data * @param next */ public Node(Object data, Node next) { this.data = data; this.next = next; } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。