java uses linked list to realize Joseph ring
- 2021-07-24 10:56:05
- OfStack
Joseph's ring is a mathematical application problem: people known as n (denoted by numbers 1, 2, 3... n respectively) sit around a round table. Start counting from the person numbered k, and the person who counts to m is listed; His next person started counting from 1, and the person who counted to m went out again; Repeat this rule until all the people around the round table are out of line. Find the queue sequence.
Using linked list, node data is the number.
package com.dm.test;
public class Test2
{
public static void main(String[] args)
{
// Head node
Node root = new Node(1);
int[] order = build(root,9,5);
for(int i =0;i<order.length;i++)
{
System.out.print(order[i]+" ");
}
}
// Build Joseph Ring 1 Linked list
public static int[] build(Node root,int n, int m)
{
Node current = root;
for(int i = 2; i<=n; i++)
{
Node node = new Node(i);
current.next = node;
current = node;
}
current.next = root;
int[] order = come(root,n,m);
return order;
}
// Out of queue
// End condition: Only 1 Node, the of this node next Is itself
// Put the number out in 1 Of the arrays, the traversal array is the queue sequence
public static int[] come(Node root,int n, int m)
{
int[] order = new int[n];
int j = 0;
Node p = root;
while(p.next!=p)
{
int i = 1;
while(i<m-1)
{
p=p.next;
i++;
}
if(i==m-1)
{
order[j]=p.next.data;
j++;
p.next = p.next.next;
p=p.next;
}
}
order[j]=p.data;
return order;
}
}
class Node
{
int data;
Node next;
public Node(int data)
{
this.data = data;
next= null;
}
}