## Tuesday, July 9, 2019

### Detect And Remove Loop In A LinkedList

Detect And Remove Loop In A LinkedList Or Remove loop from a linked list.
Steps:
• First you need to check for loop in linked list.
• To check loop. you need to take two pointers prePointer and nextPointer, prePointer will be slow and next pointer will be fast.
• once prePointer == nextPointer that means linked list has loop.
• slow pointer will move one step
• faster pointer will move two steps
• set prePointer to NULL

```

Node startNode;

public static void main(String[] args) {

Node n1 = new Node(10);
Node n2 = new Node(20);
Node n3 = new Node(30);
Node n4 = new Node(40);
Node n5 = new Node(50);
Node n6 = new Node(60);
Node n7 = new Node(70);
Node n8 = new Node(80);

g.startNode = n1;

n1.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
n5.setNext(n6);
n6.setNext(n7);
n7.setNext(n8);
n8.setNext(n6);

// Detect and Remove Loop in a Linked List
g.printList(newStart);
}

private static Node detectAndRemoveLoopInLinkedList(Node startNode) {
Node slowPointer = startNode;
Node fastPointer = startNode;
Node previousPointer = null;

while (fastPointer != null && fastPointer.getNext() != null) {
slowPointer = slowPointer.getNext();
previousPointer = fastPointer.getNext(); // For capturing just previous node of loop node for setting it to
// null for breaking loop.
fastPointer = fastPointer.getNext().getNext();

if (slowPointer == fastPointer) { // Loop identified.
slowPointer = startNode;

// If loop start node is starting at the root Node, then we slowpointer,
// fastpointer and head all point at same location.
// we already capture previous node, just setting it to null will work in this
// case.
if (slowPointer == fastPointer) {
previousPointer.setNext(null);

} else {
// We need to first identify the start of loop node and then by setting just
// previous node of loop node next to null.
while (slowPointer.getNext() != fastPointer.getNext()) {
slowPointer = slowPointer.getNext();
fastPointer = fastPointer.getNext();
}
fastPointer.setNext(null);
}
}
}
return startNode;
}

private void printList(Node startNode) {
while (startNode != null) {
System.out.print(startNode.getData() + " ");
startNode = startNode.getNext();
}
}

}
```
```package linkelist.example;

public class Node {

private int data;
private Node next;

public Node(int data) {
this.data = data;
}

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}
}

```
Output:
```
10 20 30 40 50 60 70 80
```
Related Tutorials