環形單連結清單實作——約瑟夫問題

本文主要是借助環形連結清單解決約瑟夫環問題，約瑟夫問題是，設編号為1，2，...n的n個人圍坐成一圈，約定編号為k（1<=k<=n) 的人從1開始報數，數到m的那個人就出列，依次類推，直到所有都出列為止，由此産生一個出隊的序列。

提示：用一個不帶頭結點的循環連結清單來處理該問題，先構成一個有n個節點的單循環連結清單，然後由k節點起從1開始計數，計到m是，對應節點從連結清單中删除，然後再從被删除節點的下一個節點又從1開始計數，直到最後一個節點從連結清單中删除，算法結束。

1，環形連結清單的添加（建立）

首先定義一個first節點（剛進傳入連結表的節點），不放具體的資料，當添加的是第一個節點的時候，将添加之後的節點的next指向自己，除了第一個節點之外，其他添加的節點都是将單連結清單中最後的一個節點的next指向要添加的節點，然後将添加之後的節點的next指向first，即第一個節點，形成環狀。

2，環形連結清單的周遊

環形連結清單周遊結束的一個标志是當循環到最後一個節點的next = first時，就表示該連結清單已經周遊結束。

3，環形連結清單出隊順序

根據使用者的輸入，生成一個小孩的出圈順序，例如n=5，有5個小孩圍成一圈，k=1，從第一個人開始報數，m=2，數兩下，報數為2的小孩出圈，然後又從第3個小孩開始報數，報數1，計數兩次，依次類推。

1，建立一個輔助指針（變量）helper,事先應該指向環形連結清單的最後這個節點。

2，當小孩報數時，讓first和helper指針同時移動m-1次。這句話的了解是，比如從1開始報數，報兩次，1報了1後，2報數2，本身first指向1，隻需要移動一次就行了，是以是m-1次。而helper也要跟着移動。

3，這時就可以将first指向的小孩節點出圈，具體操作是first = first.next，helper.next = first

4，原來移除的節點沒有任何引用，将會被垃圾回收機制回收。

代碼實作

package cn.mrlij.linkedlist;

/**
 * 環形單連結清單的實作_約瑟夫環問題
 * 
 * @author dreamer
 *
 */
public class Josepfu {
	public static void main(String[] args) {
		CircleSingleLinkedList c = new CircleSingleLinkedList();
		c.addBoy(5);
//		c.show();
		c.countBoy(1, 2, 5);
	}

}

class CircleSingleLinkedList {
	private Boy first = new Boy(-1);// 建立第一個小孩，不放任何資料
	// 添加小孩

	/**
	 * 根據使用者的輸入，計算小孩的出圈順序
	 * 
	 * @param startNo
	 * @param countNum
	 * @param nums
	 */
	public void countBoy(int startNo, int countNum, int nums) {
		// 判斷參數的合理性
		if (first == null || startNo < 1 || countNum < 1 || countNum > nums || nums < 1) {
			System.out.println("參數錯誤！");
			return;
		}
		// 1,建立環形連結清單輔助指針，事先指向連結清單最後的一個節點；
		Boy helper = first;
		// 周遊查找到最後的節點
		while (true) {
			if (helper.getNext() == first) {
				break;
			}
			helper = helper.getNext();
		}
		// first 和 helper都找到之後，處理從第幾個位置開始數，将first和helper

		// 分别移動startNo - 1 次
		for (int i = 0; i < startNo - 1; i++) {
			first = first.getNext();
			helper = helper.getNext();
		}
		while (true) {
			if (helper == first) {
				break;
			}
			// 2,當小孩報數時，分别将first 和helper 移動countNum-1次
			for (int i = 0; i < countNum - 1; i++) {
				first = first.getNext();
				helper = helper.getNext();
			}
			System.out.println("目前出圈的小孩是：" + first.getNo());
			// 3,将目前first指向的小孩移除
			first = first.getNext();
			helper.setNext(first);
		}
		System.out.println("最後留在圈中的小孩是：" + first.getNo());
	}

	public void addBoy(int nums) {
		if (nums < 1) {
			System.out.println("添加的小孩數量必須大于1");
			return;
		}
		Boy curBoy = null;// 定義輔助指針，便于操作連結清單
		for (int i = 1; i <= nums; i++) {
			Boy b = new Boy(i);// 根據索引建立孩子
			// i=1時，建立first節點，并将該節點指向自己
			if (i == 1) {
				first = b;
				first.setNext(first);
				curBoy = first;
			} else {
				// 不停的向後面添加節點，并将節點指向first節點
				curBoy.setNext(b);
				b.setNext(first);
				curBoy = b;
			}
		}
	}

	// 周遊環形連結清單 --判斷條件：當最後一個節點指向自己的時候就表示已經周遊完了
	public void show() {
		Boy cur = first;
		while (true) {
			System.out.println("小孩的編号是：" + cur.getNo());
			if (cur.getNext() == first) {
				break;
			}

			cur = cur.getNext();

		}
	}
}

class Boy {
	private int no;
	private Boy next;

	public Boy(int no) {
		super();
		this.no = no;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public Boy getNext() {
		return next;
	}

	public void setNext(Boy next) {
		this.next = next;
	}

	@Override
	public String toString() {
		return "Boy [no=" + no + "]";
	}

}