Posts Remove loop in Linked List (geeksforgeeks - SDE Sheet)
Post
Cancel

Remove loop in Linked List (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given the head of a linked list that may contain a loop. A loop means that the last node of the linked list is connected back to a node in the same list. So if the next of the previous node is null. then there is no loop. Remove the loop from the linked list, if it is present (we mainly need to make the next of the last node null). Otherwise, keep the linked list as it is.

geeksforgeeks

SOLUTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {

    public static void removeLoop(Node head) {

        // store previously visited nodes
        Set<Node> set = new HashSet<>();

        // for traversing the list
        Node temp = head;

        while(temp != null){

            // next node
            Node nextNode = temp.next;

            // if the current node points to the next node
            // and that next node was already visited
            // we know, there is a loop
            // we can break the loop by removing the link from current to the next node
            if(set.contains(nextNode)){
                temp.next = null;
                break;
            }else
            // otherwise, add the current node to the visited list
                set.add(temp);

            // go to the next node
            temp = temp.next;

        }

    }

}
This post is licensed under CC BY 4.0 by the author.