Remove Loop From Linked List Editorial

Practice Problem Link: Remove Loop From Linked List

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

Problem Statement

Given a linked list, remove the loop if it exists. 

You need to find the last node of the list that points to one of its previous nodes and make it point to 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. So set the next pointer of the previous node of fastPtr to NULL.

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;
	}
};
*/

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

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
	
class Solution {
	void removeLoop(ListNode list) {
	    if (list == null || list.next == null) {
			return;
		}
		ListNode slowPtr = list.next, fastPtr = list.next.next;
		ListNode prevNode = list.next;
		while (fastPtr != null && fastPtr.next != null) {
			if(slowPtr == fastPtr) {
				slowPtr = list;
				break;
			}
			slowPtr = slowPtr.next;
			prevNode = fastPtr.next;
			fastPtr = fastPtr.next.next;
		}
		if (fastPtr == null || fastPtr.next == null) {
			return;
		}
		while (slowPtr != fastPtr) {
			prevNode = fastPtr;
			slowPtr = slowPtr.next;
			fastPtr = fastPtr.next;
		}
		prevNode.next = null;
		return;
	}
}

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 that specific node is the start of the loop. So set the next pointer of the previous node to NULL.

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;
	}
};
*/

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

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
	
class Solution {
	void removeLoop(ListNode list) {
	    HashMap<ListNode, Integer> visitedNodes = new HashMap<ListNode, Integer> ();
		ListNode currentNode = list;
		ListNode prevNode = null;
		while(currentNode != null) {
			if (visitedNodes.get(currentNode) == null) {
				visitedNodes.put(currentNode, 1);
			} else {
				prevNode.next = null;
				break;
			}
			prevNode = currentNode;
			currentNode = currentNode.next;
		}
		return;
	}
}