收集面试题（九）（取得链表的指定数）

public class NodeTest {

	/** 得到Node，两个元素，一个为值，一个为指向下个值的指针。 */
	static private class Node {

		public int data;

		public Node nextNode;
	}

	/**得到链表的总数，正向计数得到总数-k*/
	private static int findNode(Node headNode, int k) {

		int count = 0;
		Node node = headNode;
		while (node.nextNode != null) {
			count++;
			node = node.nextNode;
		}

		if (k >= count) {
			return 0;
		}
		node = headNode;
		for (int i = 0, t = count - k; i <= t; i++) {

			if (i == t) {
				System.out.println(node.data);
				return 1;
			} else {
				node = node.nextNode;
			}
		}

		return 0;
	}

	/**取得两个指针，一个计数到k，另一个开始，第一个结束时，第2个取得。*/
	private static int findNodeOther(Node headNode, int k) {

		Node node1 = headNode;

		Node node2 = headNode;

		for (int i = 0; i < k && node1.nextNode != null; i++) {
			node1 = node1.nextNode;
		}

		if (node1.nextNode == null) {
			return 0;
		}
		while (node1.nextNode != null) {
			node1 = node1.nextNode;
			node2 = node2.nextNode;
		}
		System.out.println(node2.data);
		return 1;
	}

	/** 测试用 */
	public static void main(String[] args) {

		Node headNode = new Node();
		Node node = headNode;

		/** 生成node链表 */
		for (int i = 0; i < 120; i++) {
			node.nextNode = new Node();
			node.nextNode.data = i * 4;

			node = node.nextNode;
		}

		node.nextNode = null;

		System.out.println(findNode(headNode, 120));
		System.out.println(findNodeOther(headNode, 120));
	}
}