Given a list, return the node where the cycle begins. If there is no cycle, return null

Consider example 1->2->3->4->1 returns 1.

Consider example 1->2->3->4 returns null.

The problem can be solved by having slow and fast pointer.

• Increment slow pointer once and increment fast pointer twice.
• Check whether the node at slow and fast pointer is same.
• If the nodes are same, move the slow pointer to start of the list.
• Increment slow and fast pointer. Check the nodes, if its same return the node.

The LinkedList for the example is singly. Here is how Node class looks like:

class Node {
	int value;
	public Node next;
	
	public Node(int value) {
		this.value = value;
	}	
}

public class LinkedListCycle {

	public boolean hasCycle(Node head) {
        if(head==null) return false;
		Node slow = head;
		Node fast = head;
		boolean isCycle = false;
		while(slow.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
			if(slow == fast) {
				isCycle = true;
				break;
			}
		}
		if (!isCycle)
			return null;
		fast = head;
		while (slow != fast) {
			slow = slow.next;fast = fast.next;
		}
		return fast;	
    }
}