[CC150][2.6] Given a circular linked list, implement an algorithm which returns node at the beginning of the loop DEFINITION Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.EXAMPLE input: A -> B -> C -> D -> E -> C [the same C as earlier] output: C

CircularList.java

import java.util.Random;
import java.util.HashSet;

public class CircularList<Item> {
	private Node first;
	private Node last;
	
	private class Node {
		private Item item;
		private Node next;
	}
	
	public CircularList(Item[] items, int loopStartIdx) {
		Node curr, loopStart = null;
		for (int i = 0; i < items.length; i++) {
			curr = new Node();
			curr.item = items[i];
			if (i == loopStartIdx)
				loopStart = curr;
			if (i == 0) {
				first = curr;
				last = first;
				continue;
			}
			last.next = curr;
			last = curr;		
		}
		last.next = loopStart;
	}
	
	public Item findCircle() {
		Node curr = first;
		HashSet<Integer> set = new HashSet<Integer>();
		while (curr != null) {
			if (!set.add(curr.hashCode()))
				return curr.item;
			else curr = curr.next;
		}
		return null;
	}
	
	public static void main(String[] args) {
		Integer data[] = {0,1,2,3,4,5,6,7,8,9,10};
		CircularList<Integer> test = new CircularList<Integer>(data, 0);
		System.out.println(test.findCircle().toString());
	}
}