Detect and Remove Loop
Given a singly linked list, you have to detect the loop and remove the loop from the linked list, if present. You have to make changes in the given linked list itself and return the updated linked list.

Expected Complexity: Try doing it in O(n) time complexity and O(1) space complexity. Here, n is the number of nodes in the linked list.

Input format:

The first line of input contains two values: the number of nodes in the linked list and the value of the kth node from which the last node connects to form the loop while the second line of input contains the given linked list. The value of k should be greater than or equal to 0 and less than equal to n. For, k equal to 0, there is no loop present in the linked list and for k equal to n, the last node is connected to itself to form the cycle.

Output Format:

The only output line contains the linked list after removing the loop if present.

Constraints:

1

Question

Detect and Remove Loop

Given a singly linked list, you have to detect the loop and remove the loop from the linked list, if present. You have to make changes in the given linked list itself and return the updated linked list.

Expected Complexity: Try doing it in O(n) time complexity and O(1) space complexity. Here, n is the number of nodes in the linked list.

Input format:

The first line of input contains two values: the number of nodes in the linked list and the value of the kth node from which the last node connects to form the loop while the second line of input contains the given linked list.
The value of k should be greater than or equal to 0 and less than equal to n. For, k equal to 0, there is no loop present in the linked list and for k equal to n, the last node is connected to itself to form the cycle.

Output Format:

The only output line contains the linked list after removing the loop if present.

Constraints:

1 <= N <= 100000.
1 <= ‘VAL’ <= 1000 .  

Time limit: 1 sec

Accepted Answer

Fix algorithm to solve the problem. Its standard. Used 2 pointer approach (slow-fast)

Accepted Answer

Outer And Inner Loop

We are going to have two loops outer-loop and inner-loop

Maintain a count of the number of nodes visited in outer loop.
For every node of the outer-loop, start the inner loop from the head and maintain a prev node to store the previous node of the current outer loop node.
If the inner-loop visits the node next to the outer-loop node, then a cycle exist,we will simply set the prev node's next as NULL that will break the cycle and return the linked list else repeat the process for the next iteration of outer-loop.
If outer-loop reaches the end of list or null, then no cycle exist, return head.

Space Complexity: O(1)Explanation:

O(1), As we are not using any memory to store anything.

Time Complexity: O(n^2)Explanation:

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

For every iteration of outer-loop we are iterating the linked-list again.

Java (SE 1.8)

/*
    Time Complexity: O(N^2)
    Space Complexity: O(1)

    where 'N' is the number of nodes in the list.   
*/

import java.util.ArrayList;

public class Solution {
  public static Node removeLoop(Node head) {
    int numberOfNodesPassed = 0; 
    Node prev = null;
    Node outerLoopNode = head;
    while (outerLoopNode != null) {

        numberOfNodesPassed += 1;
        prev = outerLoopNode;
        outerLoopNode = outerLoopNode.next; 
        Node innerLoopNode = head;
        int counterForInnerLoop = numberOfNodesPassed; 

        while (counterForInnerLoop > 0){
        
            //  We found a repetitive Node/ Cycle
            if (innerLoopNode == outerLoopNode){

                prev.next = null;
                return head;
            }

            innerLoopNode = innerLoopNode.next; 
            counterForInnerLoop -= 1;
        }
    }

    // We didn't found any Cycle.
    return head;
  }
}

C++ (g++ 5.4)

/*
    Time Complexity: O(N^2)
    Space Complexity: O(1)

    where ‘N’ is the number of nodes in the list.   
*/

Node *removeLoop(Node *head)
{
    int numberOfNodesPassed = 0; 
    Node *prev = nullptr;
    Node *outerLoopNode = head;
    while (outerLoopNode != nullptr) {

        numberOfNodesPassed += 1;
        prev = outerLoopNode;
        outerLoopNode = outerLoopNode->next; 
        Node *innerLoopNode = head;
        int counterForInnerLoop = numberOfNodesPassed; 

        while (counterForInnerLoop){
        
            //  We found a repetitive Node/ Cycle
            if (innerLoopNode == outerLoopNode){

                prev->next = nullptr;
                return head;
            }

            innerLoopNode = innerLoopNode->next; 
            counterForInnerLoop -= 1;
        }
    }

    // We didn't found any Cycle.
    return head;
}

Python (3.5)

"""

    Time Complexity: O(N*N)

    Space Complexity: O(1)



    where ‘N’ is the number of nodes in the list.   

"""



from typing import *



class Node:



    def __init__(self, val):

        self.val = val

        self.next = None



def removeLoop(head :Node) -> Node :



    numberOfNodesPassed = 0 

    prev = None

    outerLoopNode = head

    while (outerLoopNode != None) :



        numberOfNodesPassed+=1

        prev = outerLoopNode

        outerLoopNode = outerLoopNode.next 

        innerLoopNode = head

        counterForInnerLoop = numberOfNodesPassed 



        while (counterForInnerLoop) :

        

            #  We found a repetitive Node/ Cycle

            if (innerLoopNode == outerLoopNode) :



                prev.next = None

                return head 



            innerLoopNode = innerLoopNode.next 

            counterForInnerLoop -= 1

    



    #  We didn't found any Cycle

    return head

Accepted Answer

Look Up Table Approach

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

Visit every node one by one, until null is not reached.
Declare ‘PREV’ that will store the previous node of the current node.
Check if the current node is present in the loop up table, if present then there is a cycle and will set the next value of ‘PREV’ node as NULL that will break the cycle and return the linked list otherwise, put the node reference into the lookup table update the ‘PREV’ node and repeat the process.
If we reach at the end of the list or null, then we can come out of the process or loop, and finally, we can say the loop doesn't exist.

Space Complexity: O(n)Explanation:

O(N), Where N is the total number of nodes.

At most we will put all the N nodes into the loop up table.

Time Complexity: O(n)Explanation:

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

We would be visiting every node once, as soon as we encounter a multiple visit on a node, then we will stop execution.

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' is the number of nodes in the list.   
*/

import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;

public class Solution {
  public static Node removeLoop(Node head) {
    // LookUp table to store the visited nodes.    
    Set lookUp = new HashSet();

    Node prev = null;
    Node cur = head;

    while (cur != null){

        if (lookUp.contains(cur)){
            // We reached some earlier node again thus we found a cycle
            prev.next = null;
            return head;
        }
        else{
            // Add the node to hastset of already seen nodes
            lookUp.add(cur);
            prev = cur;
        }

        cur = cur.next;
    }

    // We didn't found any Cycle
    return head;
  }
}

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where ‘N’ is the number of nodes in the list.   
*/

#include 
Node *removeLoop(Node *head)
{
    // LookUp table to store the visited nodes.
    set lookUp;

    Node *prev = nullptr;
    Node *cur = head;

    while (cur != nullptr){

        if (lookUp.find(cur) != lookUp.end()){
            //  We reached some earlier node again thus we found a cycle
            prev->next = nullptr;
            return head;
        }
        else{
            // Add the node to hastset of already seen nodes
            lookUp.insert(cur);
            prev = cur;
        }

        cur = cur->next;
    }

    // We didn't found any Cycle
    return head;
}

Python (3.5)

"""

    Time Complexity: O(N)

    Space Complexity: O(N)



    where ‘N’ is the number of nodes in the list.   

"""



from typing import *





class Node:

    def __init__(self, val):

        self.val = val

        self.next = None





def removeLoop(head: Node) -> Node:



    # LookUp table to store the visited nodes.

    lookUp = set()



    prev = None

    cur = head



    while cur != None:



        if cur in lookUp:

            #  We reached some earlier node again thus we found a cycle

            prev.next = None

            return head



        else:

            #  Add the node to hastset of already seen nodes

            lookUp.add(cur)

            prev = cur



        cur = cur.next



    #  We didn't found any Cycle

    return head

Accepted Answer

Slow And Fast Pointer Approach

The idea is to have 2 pointers: slow and fast. Slow pointer takes a single jump and corresponding to every jump slow pointer takes, fast pointer takes 2 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 fast pointer will reach the end of the linked list well before the slow pointer reaches the end or null.
Initialize slow and fast at the beginning.
Start moving slow to every next node and moving fast 2 jumps, while making sure that fast and its next is not null.
If after adjusting slow and fast, if they are referring to the same node, there is a cycle and break this loop otherwise repeat the process
If fast reaches the end or null then the execution stops and we can conclude that no cycle exists and return head pointer.
Now,to find the starting point of the cycle set fast at head and slow at current slow and move both the pointers by one step.The pointer where they meet is the starting point of the cycle.Set this node as ‘START’.
Iterate the list to find the previous node of ‘START’ and set the next of that previous node as an empty node.

Space Complexity: O(1)Explanation:

O(1), Since we don't use any extra space other than the input provided

Time Complexity: O(n)Explanation:

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

Java (SE 1.8)

/*
     Time Complexity: O(N)
    Space Complexity: O(1)

    where 'N' is the number of nodes in the list.
*/

import java.util.ArrayList;

public class Solution {
  public static Node removeLoop(Node head) {
    if (head == null || head.next == null){
        return head;
    }

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

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

    while (true){

        // We reached the end of the List and haven't found any Cycle
        if (fast == null || fast.next == null){
            return head;
        }

        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast){
            break;
        }
    }

    // Cycle Found.
    fast = head;

    // start will point the starting node of cycle.
    Node start = null;

    while (fast != slow){

        fast = fast.next;
        slow = slow.next;
    }

    start = slow;

    // Finding the previous node of 'start'.
    Node cur = start;

    while (true){

        if (cur.next == start){

            cur.next = null;
            return head;
        }

        cur = cur.next;
    }
  }
}

C++ (g++ 5.4)

/*
     Time Complexity: O(N)
    Space Complexity: O(1)

    where ‘N’ is the number of nodes in the list.
*/

Node *removeLoop(Node *head)
{
    if (head == nullptr || head->next == nullptr){
        return head;
    }

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

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

    while (true){

        // We reached the end of the List and haven't found any Cycle
        if (fast == nullptr || fast->next == nullptr){
            return head;
        }

        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast){
            break;
        }
    }

    // Cycle Found.
    fast = head;

    // start will point the starting node of cycle.
    Node *start = nullptr;

    while (fast != slow){

        fast = fast->next;
        slow = slow->next;
    }

    start = slow;

    // Finding the previous node of 'start'.
    Node *cur = start;

    while (true){

        if (cur->next == start){

            cur->next = nullptr;
            return head;
        }

        cur = cur->next;
    }

}

Python (3.5)

"""

    Time Complexity: O(N)

    Space Complexity: O(1)



    where ‘N’ is the number of nodes in the list.   

"""



from typing import *





class Node:

    def __init__(self, val):

        self.val = val

        self.next = None





def removeLoop(head: Node) -> Node:



    if head == None or head.next == None:

        return head



    #  Slow Pointer - This will be incremented by 1 Nodes

    slow = head



    #  Fast Pointer  - This will be incremented by 2 Nodes

    fast = head



    while True:



        #  We reached the end of the List and haven't found any Cycle

        if fast == None or fast.next == None:

            return head



        slow = slow.next

        fast = fast.next.next



        if slow == fast:

            break



    # Cycle Found.

    fast = head



    # start will point the starting node of cycle.

    start = None



    while fast != slow:



        fast = fast.next

        slow = slow.next



    start = slow



    # Finding the previous node of 'start'.

    cur = head



    while True:



        if cur.next == start:



            cur.next = None

            return head



        cur = cur.next

Given a singly linked list, you have to detect the loop and remove the loop from the linked list, if present. You have to make changes in the given linked list itself and return the updated linked list.

Expected Complexity: Try doing it in O(n) time complexity and O(1) space complexity. Here, n is the number of nodes in the linked list.

Input format:

Output Format:

Constraints:

Top AlphaSense Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in AlphaSense Software Developer