#CC150 #CC150-chap2 2.6 Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.

FindCircularListLoopHead.java

public class FindCircularListLoopHead{

	// Use a hashset to store the unique nodes, if we find a duplicate one we have found the head of the circular list. 
	// Time O(N), Space O(N)
	
	// Or, convert the Node object to their hashcode, check the integer to see if they are unique
	public Node findCircularHeadByHash(Node n){
		Set<Node> uniqueNodes = new HashSet<Node>();
		if(n!=null){
			if uniqueNodes.contains(n){
				return n;
			}
			uniqueNodes.add(n);
		}
		return null;
	}
	
	// Same solution as in the book, use the runner technique
	// Time O(N), Space O(1)
	public Node findCircularHeadByRunner(Node head){
		// The slow pointer moves one step at a time, the fast pointer moves two steps at a time.
		Node slow = head;
		Node fast = head;
		while(fast!=null && fast.next!=null){
			slow = slow.next;
			fast = fast.next.next;
			// Collision
			if(slow == fast){
				break;
			}
		}
		// Error check, if they did not meet ther's no loop
		if(fast==null || fast.next==null){
			return null;
		}
		// Move the slow pointer to the head, the slow one is k steps from the meeting point, the fast one is at k%loop_size. Move them at the same pace, they will meet at the beginning of the circle
		slow = head;
		while(slow!=fast){
			slow = slow.next;
			fast = fast.next;
		}
		return fast;
		
	}
}