卡片扔掉奇数位 算法

    有N张卡片，标号为从1到N。第一轮抽取到奇数位时，将卡片扔掉，偶数位保留；第二轮扔掉剩下来的奇数位。以此类推，最后剩下的卡片标号为？

1. 列表实现

private static int retrieveLastViaList(int n) {
	LinkedList<Integer> list = new LinkedList<Integer>(); // 构建列表
	for (int i = 1; i <= n; i++) { // 第一轮
		if (i % 2 == 0) {
			list.add(i); // 存放卡片
		}
	}
	boolean bOdd = true; // 奇数位标志
	Iterator<Integer> iter = list.iterator();
	while (true) {
		if (!iter.hasNext()) { // 到卡片尾部了，开始下一轮
			iter = list.iterator();
			bOdd = true; // 重置奇数位标志
		}
		Integer cur = iter.next();
		if (list.size() == 1) { // 卡片只有一张了，是我们需要的
			return cur;
		}
		if (bOdd) { // 奇数位
			iter.remove(); // 扔掉卡片
			bOdd = false; // 切换偶数位
		} else { // 偶数位
			bOdd = true; // 切换奇数位
		}
	}
}

2. 数组实现

private static int retrieveLastViaArray(int n) {
	int[] arr = new int[n]; // 构建数组
	for (int i = 1; i <= n; ++i) {
		arr[i - 1] = i; // 存放卡片
	}
	int cur = 1; // 当前卡片
	int rem = n; // 剩余卡片数
	boolean bOdd = true; // 奇数位标志
	while (true) {
		if (rem == 1) { // 只剩一张卡片
			while (arr[cur - 1] == 0) { // 该卡片已丢弃，定位下一张可用的卡片
				cur++;
				if (cur > n) { // 超过卡片尾部
					cur = 1;
				}
			}
			return cur; // 返回该卡片标号
		}
		while (arr[cur - 1] == 0) { // 该卡片已丢弃，定位下一张可用的卡片
			cur++;
			if (cur > n) { // 超过卡片尾部，开始下一轮
				bOdd = true; // 重置奇数位标志
				cur = 1;
			}
		}
		if (bOdd) { // 奇数位
			arr[cur - 1] = 0; // 置0，表示丢弃
			rem--; // 剩余卡片减一
			bOdd = false; // 切换到偶数位
		} else { // 偶数位
			bOdd = true; // 切换到奇数位
		}
		cur++;
		if (cur > n) { // 超过卡片尾部，开始下一轮
			bOdd = true; // 重置奇数位标志
			cur = 1;
		}
	}
}

逻辑方面，数组比列表复杂，因为数组创建后，长度无法改变，通过置0表示扔掉该卡片。
性能方面，数组比列表要好很多。