某互联网公司面试题(二)

public class TestCircularList {
	static class Node<T> {
		T value;
		Node<T> next;

		Node(Node<T> next, T value) {
			this.value = value;
			this.next = next;
		}

	}

	public static Node<Integer> generateLinkList(int number) {
		Node<Integer> t = new Node<Integer>(null, 0);
		Node<Integer> temp = t;
		Node<Integer> temp1 = null;
		for (int i = 1; i < number; i++) {
			temp1 = new Node<Integer>(null, i % number);
			temp.next = temp1;
			temp = temp1;
		}
		temp.next = t.next.next.next;// construct circular linked list
		return t;
	}

	public static void main(String[] args) {
		Node<Integer> node = TestCircularList.generateLinkList(10);
		TestCircularList.traverse(node, 10);
	}

	/**
	 * 
	 * @param <T>
	 * @param node
	 *            the head node
	 * @param length
	 *            the actural number of nodes of the linked list
	 */
	public static <T> void traverse(Node<T> node, int length) {
		Node<T> temp = node;
		Node<T> temp1 = null;
		while (temp != null) {
			temp1 = temp.next;
			int tailIndex = --length;
			while (temp1 != null && tailIndex != 0) {
				if (temp1 == temp) {
					System.out.println("has rings!");
					System.out.println("Begin node value: " + temp.value);
					while (temp.next != temp1) {
						System.out.println(temp.next.value);
						temp = temp.next;
					}
					System.out.println("End node value: " + temp.value);
					return;
				}
				temp1 = temp1.next;
				tailIndex--;
			}
			temp = temp.next;
		}
	}
}