Question

java循环单链表实现约瑟夫环，我的代码出列顺序不正确

import java.util.*;
public class MainJose
{
public static void main (String[] args)throws Exception
{
int m,n;
Scanner reader=new Scanner(System.in);
System.out.print("请输入参与游戏的人数：");
n=reader.nextInt();
System.out.print("请输入出列密码：");
m=reader.nextInt();
LinkList li=new LinkList();
for(int i=0;i<n;i++)
{
li.createlist(i+1);
}
System.out.println("输出检查循环链表：");
li.display();
System.out.print("出列顺序：");
li.out(m);
}
}

package shugou;
public class Node
{
private Object data;
private Node next;
public Node()
{
this(null,null);
}
public Node(Object data)
{
this(data,null);
}
public Node(Object data,Node next)
{
this.data=data;
this.next=next;
}
public Object getData()
{
return data;
}
public Node getNext()
{
return next;
}
public void setData(Object data)
{
this.data=data;
}
public void setNext(Node next)
{
this.next=next;
}
}
package shugou;
public class LinkList
{
private Node head,tail;
int curlen=0,position=-1;
//创建链表
public void createlist(int code)throws Exception
{
insert(curlen,code);
}
public void insert(int i,int code)throws Exception
{
Node s=new Node(code);
if(i==0)
{
s.setNext(head);
head=s;
}
Node p=head;
int j=0;
while(p!=null&&j<i-1)
{
p=p.getNext();
j++;
}
if(j>i||p==null)
{
throw new Exception("插入位置不合理");
}
s.setNext(p.getNext());
p.setNext(s);
tail=s;
tail.setNext(head);
curlen=curlen+1;
}
public void remove(int i)throws Exception
{
Node p=head,q=null;
int j=0;
i=i-1;
while(j<i)
{
q=p;
p=p.getNext();
j++;
}
if(j>i||p==null)
throw new Exception("删除位置不合法");
if(q==null)
{
tail.setNext(p.getNext());
head=head.getNext();
}
else q.setNext(p.getNext());
curlen=curlen-1;
}
public void out(int m)throws Exception
{
Node p=head;
int count=1;
while(curlen>0)
{
if(count==m)
{
System.out.print(p.getData()+" ");
p=p.getNext();
remove(m);
count=1;
}
else
{
p=p.getNext();
count++;
}
}

}
public void display()
{
Node node=head;
for(int i=0;i<2*curlen;i++)
{
System.out.print(node.getData()+" ");
node=node.getNext();
}
System.out.println();
}
}

Answer 1

你的remove方法不对，你的方法每次删掉的是从head开始第m个位置的节点，
但约瑟夫环需要的是要删掉每次循环数到m的位置的节点。
remove方法可以去掉，再把out方法改一下就可以了。
public void out(int m) throws Exception {
Node p = head;
Node pre = null;
int count = 1;
while (curlen > 0) {
if (count == m) {
System.out.print(p.getData() + " ");
if(pre != null){
pre.setNext(p.getNext());
}
p = p.getNext();
curlen = curlen - 1;
count = 1;
} else {
pre = p;
p = p.getNext();
count++;
}
}
}