前面我用顺序表类实现了约瑟夫环（详见顺序表之约瑟夫环），今天再用单链表来实现一下，如下：

package linearList;

public class Josephus {
	private LList<String> list;//创建线性表，用来存储元素
	
	/*
	 * 创建约瑟夫环并求解，指定其长度、起始位置、计数
	 */
	public Josephus(int number,int start,int distance){
		
		//this.list = new SeqList<String>(number);//创建指定容量的的顺序表
		this.list = new SinglyLinkedList<String>();//创建指定容量的的单链表
		
		for(int i=0;i<number;i++){
			this.list.add(new String((char)('A'+i)+""));//添加字符串对象
		}
		System.out.print("约瑟夫环("+number+","+start+","+distance+"),");
		System.out.println(this.list.toString());//显示字符串
		
		int index = start-1;//计数起始位置
		while(this.list.length()>1){//只有在多余一个对象时才执行删除操作
			index = (index+distance-1)%this.list.length();
			System.out.print("删除"+this.list.remove(index).toString()+",");
			System.out.println(this.list.toString());
		}
		System.out.println("被赦免者是："+list.get(0).toString());
	}
	
	public static void main(String[] args) {
		long startTime = System.currentTimeMillis();
		
		for(int i=0;i<10;i++)
			new Josephus(5,1,2);
		
		long endTime = System.currentTimeMillis();
		System.out.println("程序运行时间："+(endTime-startTime)+"ms");
		
	}

} 

程序运行时间：9ms

         大家可能会发现，这个实现跟顺序表实现（顺序表之约瑟夫环）基本上没什么区别，是的，算法没变，只是数据结构变了，由顺序存储结构变成了链式存储结构，而且我们发现执行的时间也是在变的。相比较之下，单链表结构的操作的时间要小于顺序表的；由于在本题中，插入和删除结点都是在指定的结点之前，所以需要遍历部分单链表，因此顺序表的时间主要消耗在移动元素上面，而单链表的时间主要消耗在了遍历结点上面，从时间复杂度来看，顺序表是O(n)，单链表在最坏的情况下是O(n);在同等条件下测试之后发现，顺序表13ms，单链表9ms，这也就说明本题中遍历的只是部分单链表。对于单链表的改进可以提高效率，后面我会继续介绍。