最近学数据结构，看到约瑟夫环这一块就卡住了...感觉好难，书上的练习题叫我直接用链表实现，可是一开始的思路都没有，看了很多其他高手的代码也不是很明白，后来想想还是先用简单的数组试着写写看。
可能是我对链表的理解还不是很透彻，数组写了半天。。。差不多也能大概的实现了，很复杂，可读性也不好........但毕竟实现了，通过数组实现的经验之后，链表也开始有点思路起来。再在网上搜了一些高手的代码，慢慢的，链表实现的环也成型了。
再回头看看，其实逻辑也不是很复杂，当初的可能真是对链表不是很理解，对约瑟夫环的理解也可能只是停留在数组这一块。。。真没想到原来链表实现的环效率高了不是一点半点。。。
废话不多说（虽然已经说了很多了。。。） 贴码：
package com;
public class LinkRing {
int data;
LinkRing next;
public LinkRing(int data){
this.data = data;
this.next = null;
}
//测试
public static void main(String[] args) {
LinkRingList a = new LinkRingList();
//步进
int num = 4;
//节点总数
int count = 20;
//创建长度为20的环
a.cNode(count);
a.delNode(num, count);
}
}
class LinkRingList{
LinkRing last;
//创建节点 date节点数
void cNode(int date){
if(date<1)
return;
//创建一个节点
LinkRing node = new LinkRing(date);
//将这个节点设为最后一个节点
last = node;
//指向自己
last.next = last;
//创建一个临时节点用来存储第一个节点 (最后一个节点的后一个节点)
LinkRing tempNode;
//
int i = date-1;
//循环插入节点 倒着插，显示的时候更直观
while(i>0){
LinkRing nNode = new LinkRing(i);
tempNode = last.next;
last.next = nNode;
nNode.next = tempNode;
i--;
}
}
void delNode(int num,int count){
StringBuffer sbf = new StringBuffer("删除顺序为：");
int j = 1;
//从第一个节点开始 (随便从环中取一个节点开始都可以)
LinkRing curNode = last.next;
//记录当前循环节点的前一个节点
LinkRing previous = last;
//开始
while(true){
//如果到达指定的数，进行删除操作
if(j%num==0){
sbf.append(curNode.data+", ");
//前一个节点的后一个节点-->当前节点的后一个节点
previous.next = curNode.next;
}else{
//如果没有达到指定的数，将前一个节点改变为当前节点，否则前一个节点保持不变
previous = curNode;
}
//继续
j++;
//当前节点被删除，将当前节点变为删除节点的后一个节点
curNode = curNode.next;
//如果最后只存在一个节点，则跳出循环
if(previous.equals(curNode)){
System.out.println(sbf.toString());
System.out.println("最后剩余数： "+curNode.data);
break;
}
}
}
}
数组的删除和插入很慢，每次做完这两种操作之后都可能要移动大量的数据嵌套，而双端链表就没有这方面的顾虑了，可以一直循环下去，删除直接将节点脱离就行了。
初来乍到，有很多不好的地方还望高手多多指点。