How will you remove a cycle from a linked list?

1.	How will you remove a cycle from a linked list?
Answer» One method of identifying the cycle is Floyd's cycle detect technique, popularly known as the tortoise and hare algorithm since it uses two pointers/references that move at opposite SPEEDS. If there is a cycle, after a limited number of steps, the two pointers (say, slow and fast) will point to the same element. It's interesting to note that the element where they meet will be the same distance from the loop's start (continuing to traverse the list in the same, forward direction) as the loop's start is from the list's head. That is, if the linear component of the list contains k ELEMENTS, the two pointers will meet inside a loop of length m at a location m-k from the loop's start or k elements from the loop's 'end' (of course, it's a loop, so there is no 'end' - it's just the ‘start' again). That gives us a technique to FIND the loop's beginning. Once a cycle has been detected, keep fast pointing to the element where the loop for the previous step ended, but reset slow to point back to the beginning of the list. Now, one element at a time, move each pointer. Fast will keep looping because it started inside the loop. Slow and fast will meet again after k steps (equivalent to the distance between the start of the loop and the head of the list). This will serve as a pointer to the beginning of the loop. It's now simple to set slow (or fast) to point to the loop's STARTING element and traverse the loop until slow returns to the starting element. Slow is referring to the 'last' element list at this point, and its next pointer can be adjusted to null. Implementation: Node* getLastNode(Node* head) { Node* slow = head; Node* fast = head; // find the intersection point USING Tortoise and Hare algorithm while (fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) break; } //check if there is no loop if (fast->next == NULL) { return NULL; } slow = head; // run this loop till both the references are one short of the start of the loop while (slow->next != fast->next) { slow = slow->next; fast = fast->next; } // Now the fast pointer is pointing to the start of the loop return fast;}Node* getLastNode = findStartOfLoop(head);getLastNode->next = null; Time Complexity: O(n) Space Complexity: O(1)

Answer»

One method of identifying the cycle is Floyd's cycle detect technique, popularly known as the tortoise and hare algorithm since it uses two pointers/references that move at opposite SPEEDS. If there is a cycle, after a limited number of steps, the two pointers (say, slow and fast) will point to the same element.

It's interesting to note that the element where they meet will be the same distance from the loop's start (continuing to traverse the list in the same, forward direction) as the loop's start is from the list's head. That is, if the linear component of the list contains k ELEMENTS, the two pointers will meet inside a loop of length m at a location m-k from the loop's start or k elements from the loop's 'end' (of course, it's a loop, so there is no 'end' - it's just the ‘start' again). That gives us a technique to FIND the loop's beginning.

Once a cycle has been detected, keep fast pointing to the element where the loop for the previous step ended, but reset slow to point back to the beginning of the list. Now, one element at a time, move each pointer. Fast will keep looping because it started inside the loop. Slow and fast will meet again after k steps (equivalent to the distance between the start of the loop and the head of the list). This will serve as a pointer to the beginning of the loop.

It's now simple to set slow (or fast) to point to the loop's STARTING element and traverse the loop until slow returns to the starting element. Slow is referring to the 'last' element list at this point, and its next pointer can be adjusted to null.

Implementation:

Node* getLastNode(Node* head) { Node* slow = head; Node* fast = head; // find the intersection point USING Tortoise and Hare algorithm while (fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) break; } //check if there is no loop if (fast->next == NULL) { return NULL; } slow = head; // run this loop till both the references are one short of the start of the loop while (slow->next != fast->next) { slow = slow->next; fast = fast->next; } // Now the fast pointer is pointing to the start of the loop return fast;}Node* getLastNode = findStartOfLoop(head);getLastNode->next = null;

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

How will you remove a cycle from a linked list?

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment