Find cycle in Linked List

© Parineeth M R

Question 9. Find out if there is a cycle in a linked list. Also find the node where the cycle begins


We can maintain the is_visited field in each node. Initially the is_visited field in all the nodes is set to 0. When a node is traversed in the linked list, the is_visited field is changed from 0 to 1. While traversing the linked list, the moment we encounter a node whose is_visited field is already 1, we know that there is a cycle in the linked list and the cycle begins at this node. The drawback of this approach is that it uses additional memory.

To solve the problem without using additional memory, we use the following idea. Suppose two runners take part in a race, one of them being faster than the other, the faster runner will overtake the slower runner as soon as the race starts. If the race track is a loop, then later in the race, the faster runner will again meet the slower runner and overtake him. Similarly, we can traverse the linked list using a fast pointer and a slow pointer. At each step, the fast pointer is moved ahead by 2 nodes, whereas the slow pointer is moved ahead by 1 node. If there is a loop in the linked list, the two pointers will meet at a common node.

To find where the loop starts, we need to do the following: Let n1 be the fast pointer and n2 be the slow pointer. When n1 and n2 meet, initialize a third pointer n3 to point to the beginning of the linked list. So n1 is ahead of n3 in the linked list. Now ignore n2 and advance n1 and n3 one node at a time. The node where n1 and n3 meet is where the loop starts.

C/C++

/*head: first node of the linked list 
Return value: first node in loop if loop exists, NULL otherwise
*/
struct node* find_loop( struct node *head) 
{
	struct node *n1 = head, *n2 = head, *n3;
	int found_loop = 0;

	/*n1 is the fast pointer. So advance it by two steps
	n2 is slow pointer. So advance it by one step
	*/
	while (n1 != NULL) {
		n1 = n1->next;
		if (n1) {
			n1 = n1->next;
			n2 = n2->next;
		}

		/*If n1 and n2 meet then there is a loop in the linked list*/
		if (n1 == n2) {
			found_loop = 1;
			break;
		}
	}
	
	if (!found_loop)
		return NULL;

	/*Find the beginning of the loop*/
	n3 = head;
	while (n1 != n3) {
		n1 = n1->next;
		n3 = n3->next;
	}
	
	return n1;
}



Java


/*head: first node of the linked list 
Return value: first node in loop if loop exists, null otherwise
*/
public static LinkedListNode findLoop( LinkedListNode head)  {
	LinkedListNode n1 = head, n2 = head;
	boolean foundLoop = false;

	/*n1 moves fast. So advance it by two steps
	n2 is slow. So advance it by one step
	*/
	while (n1 != null) {
		n1 = n1.next;
		if (n1 != null) {
			n1 = n1.next;
			n2 = n2.next;
		}

		/*If n1 and n2 meet then there is a loop in the linked list*/
		if (n1 == n2) {
			foundLoop = true;
			break;
		}
	}

	if (!foundLoop)
		return null;

	/*Find the beginning of the loop*/
	LinkedListNode n3 = head;
	while (n1 != n3) {
		n1 = n1.next;
		n3 = n3.next;
	}

	return n1;
}



Python


#head: first node of the linked list 
#Return value: first node in loop if loop exists, None otherwise
@staticmethod
def find_loop(head): 
	n1 = n2 = head
	found_loop = False

	#n1 moves fast. So advance it by two steps
	#n2 is slow. So advance it by one step
	while (n1): 
		n1 = n1.next
		if (n1): 
			n1 = n1.next
			n2 = n2.next
	
		#If n1 and n2 meet then there is a loop in the linked list
		if (n1 == n2): 
			found_loop = True
			break
	
	if (not found_loop):
		return None
	
	#Find the beginning of the loop
	n3 = head
	while (n1 != n3):
		n1 = n1.next
		n3 = n3.next

	return n1