Detect Loop in Linked List Editorial

Practice Problem Link: Detect Loop In Linked List

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a linked list which can have a loop, find the node at which the loop starts. If no loop exists, return NULL.

Approach

• Let's say that the cyclic part of the list has length x and the non-cyclic part has length y. 
• Let's define two pointers to traverse the list, slowPtr and fastPtr, where slowPtr moves one node at a time and fastPtr moves two nodes at a time. If the list contains a loop then both the pointers must meet at a node inside the loop. Let's say this node is at a distance d from the start node of the loop.
• When both the pointers point at the same node, it will give us:

        y + rf  * x + d = 2 *(y + rs * x +d)

        i,e y + d = (rf - 2*rs ) * x    

        where rf is the number of complete cycles by fastPtr and rs is the number of complete cycles by slowPtr.

• From the above equation, it can be concluded that y+dis a multiple of x.
• Set the slowPtr to the start of the list and now move both the pointers one node at a time. The node at which they meet will be the start of the loop.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/

ListNode* getStartingNodeOfLoop(ListNode* list){
	if (list->next == NULL) {
		return NULL;
	}
	ListNode *slowPtr = list->next, *fastPtr = list->next->next;
	while (fastPtr != NULL && fastPtr->next != NULL) {
		if(slowPtr == fastPtr) {
			slowPtr = list;
			break;
		}
		slowPtr = slowPtr->next;
		fastPtr = fastPtr->next->next;
	}
	if (fastPtr == NULL || fastPtr->next == NULL) {
		return NULL;
	}
	while (slowPtr != fastPtr) {
		slowPtr = slowPtr->next;
		fastPtr = fastPtr->next;
	}
	return slowPtr;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/

class Solution {
	ListNode getStartingNodeOfLoop(ListNode list){
		if (list.next == null) {
			return null;
		}
		ListNode slowPtr = list.next, fastPtr = list.next.next;
		while (fastPtr != null && fastPtr.next != null) {
			if(slowPtr == fastPtr) {
				slowPtr = list;
				break;
			}
			slowPtr = slowPtr.next;
			fastPtr = fastPtr.next.next;
		}
		if (fastPtr == null || fastPtr.next == null) {
			return null;
		}
		while (slowPtr != fastPtr) {
			slowPtr = slowPtr.next;
			fastPtr = fastPtr.next;
		}
		return slowPtr;
	}
}

Another Approach

The idea is to hash every node address that is encountered while traversing the linked list using a hashmap and if a node address is encountered again then return that specific node address as the start of the loop.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/

ListNode* getStartingNodeOfLoop(ListNode* list){
	unordered_map<ListNode*, int> visitedNodes;
	ListNode* currentNode = list;
	while(currentNode != NULL) {
		if (visitedNodes[currentNode] == 0) {
			visitedNodes[currentNode] = 1;
		} else {
			return currentNode;
		}
		currentNode = currentNode->next;
	}
	return NULL;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/

class Solution {
	ListNode getStartingNodeOfLoop(ListNode list){
		HashMap<ListNode, Integer> visitedNodes = new HashMap<ListNode, Integer> ();
		ListNode currentNode = list;
		while(currentNode != null) {
			if (visitedNodes.get(currentNode) == null) {
				visitedNodes.put(currentNode, 1);
			} else {
				return currentNode;
			}
			currentNode = currentNode.next;
		}
		return null;
	}
}