使用链表实现环结构以解决约瑟夫环问题

        自从上次面试后，发现自己的基础很不行，应该说一直不行(因为是电信专业的，只学过简单地VB和C，当然这只是一个借口而已)。总之，决定以后争取每天写个小程序动动脑筋，东西可能写的很烂。但是只要动脑筋的目的达到了，也就没有什么好计较了得。  

       今天写的是一个关于约瑟夫环的问题。关于约瑟夫环，百度复制一下：约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

      先定义一个节点类Node：

package com.wly.linkedcirclelist;

/**
 * 节点类
 * @author wly
 *
 */
public class Node {

	private int id;
	private Node next;
	
	public Node(int id) {
		super();
		this.id = id;
	}
	
	public int getId() {
		return id;
	}
	public void setId(int id) {
		this.id = id;
	}
	public Node getNext() {
		return next;
	}
	public void setNext(Node next) {
		this.next = next;
	}
}
           

       再定义一个链表类Linkedcirclelist：

package com.wly.linkedcirclelist;

/**
 * 单项"环"型链表
 * @author wly
 *
 */
public class LinkedCircleList {

	private Node firstNode; //头节点
	private Node lastNode; //尾节点
	private int size; //这里置了一个标记size，也可以通过遍历得到长度，但是那样可能比较耗时，现在这样做的话，在多线程时可能会出问题。
	
	public LinkedCircleList() {
		size = 0;
	}
	
	/**
	 * 向链表的尾部添加节点
	 * @param node
	 */
	public void addNode(Node node) {
		if(isEmpty()) {
			firstNode = node;
			lastNode = node;
		} else {
			//将首尾节点连接，是链表变成一个"环"结构
			lastNode.setNext(node);
			node.setNext(firstNode);
			lastNode = node;
		}
		size ++;
	}
	
	/**
	 * 删除和当前节点相距n个节点的那个节点
	 * @param node 当前开始报数的节点
	 * @param n 报数步长
	 * @return
	 */
	public Node deleteAfterN(Node node,int n) {
		for(int i=n-2;i>0;i--) {
			node = node.getNext();
		}
		//删除节点
		System.out.println("删除节点:" + node.getNext().getId());
		node.setNext(node.getNext().getNext());
		size --;
		return node.getNext();
	}
	
	
	public int size() {
		return size;
	}
	
	public boolean isEmpty() {
		return (firstNode == null);
	}
	
	public Node getFirstNode() {
		return firstNode;
	}
}
           

        最后测试一下，新建Test类：

package com.wly.linkedcirclelist;

public class Test {

	public static void main(String[] args) {
		resolve(9, 1, 5);
	}
	
	public static void resolve(int n,int startIndex,int step) {
		
		//1.创建链表
		LinkedCircleList linkedList = new LinkedCircleList();
		for(int i=1;i<=n;i++) {
			Node node = new Node(i);
			linkedList.addNode(node);
		}
		//2.循环处理
		Node node = linkedList.getFirstNode();
		while(linkedList.size() > 0) {
			node = linkedList.deleteAfterN(node, step);
		}
	}
}
           

测试结果:

删除节点:5

删除节点:1

删除节点:7

删除节点:4

删除节点:3

删除节点:6

删除节点:9

删除节点:2

删除节点:8

转帖请保留出处:http://blog.csdn.net/u011638883/article/details/11783793