To detect the first node of a cycle in a singly linked list, we can use the Floyd's Tortoise and Hare algorithm.

• Use two pointers, slow and fast, to traverse the linked list.

• If there is a cycle, the fa...read more

The basic idea of this approach is to check each node as the starting point for the cycle.

Now consider the following steps:

• We are going to have two loops outer-loop and inner-loop...read more

We are going to maintain a lookup table(a HashSet) that basically tells if we have already visited a node or not, during the course of traversal.

• Visit every node one by one, unt...read more

The basic idea of this approach is to use the technique based on two-pointers (slow and fast). Slow pointer takes a single jump and corresponding to every jump slow pointers take, fast pointer takes two jumps. If there exists a cycle, both slow and fast pointers will reach the exact same node. If there is no cycle in the given linked list, then the fast pointer will reach the end of the linked list well before the slow pointer reaches the end or null.

To get the starting point of the loop we can start moving both pointers again at the same speed such that one pointer (say slow) begins from the head node of the linked list and other pointers (say fast) begins from the meeting point. This time both the pointers will necessarily meet at the starting point of the loop.

You can refer to this article for more details. -----/

Now consider the following steps:

• Start traversing the linked list using two pointers (slow and fast). Here, the slow pointer will make a jump of one node and the fast pointer will make jumps of 2 nodes.
• If both pointers meet at some node then,
  • Point the slow pointer to the head node and again start iterating (this time both pointers will make a jump of 1 node).
  • Keep moving the slow and the fast pointers unit both of them meet at a common node. This common node will be the starting node of the cycle.
• If slow and fast pointers never meet i.e. the fast pointer reaches the end of the linked list then the loop doesn’t exist in the given linked list, hence we will return -1.

O(1)

We are using constant extra space. Hence, the overall space complexity is O(1).

O(N), where ‘N’ is the total number of nodes.

Since we are using a slow pointer to traverse the linked list and the slow pointer is guaranteed to travel no more than ‘N’ steps before the fast pointer either meets the slow pointer or reaches the end of the list. So, the overall time complexity will be O(N).

/*
    Time Complexity: O(N)
    Space Complexity: O(1)
    Where 'N' is the number of nodes in the linked list.

*/

public class Solution 
{
	public static Node firstNode(Node head) 
    {

		if (head == null) 
        {
			// Empty linked list.
			return null;
		}

		// Slow Pointer - This will be incremented by 1 Nodes
		Node slow = new Node(head.data);
		slow.next = head.next;

		// Fast Pointer  - This will be incremented by 2 Nodes
		Node fast = new Node(head.data);
		fast.next = head.next;

		do 
        {
			if (fast != null && fast.next != null) 
            {
				fast = fast.next.next;
			} else 
            {
				// Fast pointer reached the end of the list.
				return null;
			}

			slow = slow.next;
		} while (fast != slow);

		slow = head;

		// To track the position of node.
		while (slow != fast) 
        {
			slow = slow.next;
			fast = fast.next;
		}
		return slow;
	}
}

'''
    Time Complexity: O(N)
    Space Complexity: O(1)
    Where 'N' is the number of nodes in the linked list.

'''

def firstNode(head):

    if (head == None):

        # Empty linked list.
        return None

    # Slow Pointer - This will be incremented by 1 Nodes
    slow = head

    # Fast Pointer - This will be incremented by 2 Nodes
    fast = head

    while (True):

        if (fast and fast.next):
            fast = fast.next.next

        else:

            # Fast pointer reached the end of the list.
            return None
        slow = slow.next
        if (fast == slow):
            break

    slow = head

    # To track the position of node.
    while (slow != fast):
        slow = slow.next
        fast = fast.next

    return slow

/*
    Time Complexity: O(N)
    Space Complexity: O(1)
    Where 'N' is the number of nodes in the linked list.

*/

Node *firstNode(Node *head)
{
	if (head == NULL)
	{
		// Empty linked list.
		return NULL;
	}

	// Slow Pointer - This will be incremented by 1 Nodes
	Node *slow = head;

	// Fast Pointer - This will be incremented by 2 Nodes
	Node *fast = head;

	do
	{
		if (fast && fast->next)
		{
			fast = fast->next->next;
		}
		else
		{
			// Fast pointer reached the end of the list.
			return NULL;
		}

		slow = slow->next;
	} while (fast != slow);

	slow = head;

	// To track the position of node.
	while (slow != fast)
	{
		slow = slow->next;
		fast = fast->next;
	}
	return slow;
}