,

## Thursday 12 February 2015

### Intersection Point of Loop in Singly Linked List

Problem Statement:
To find the intersection point of loop in a non null ending singly linked list.

Solution:
We are using the Node class and the SinglyLinkedList class for implementing singly linked list in java.

Demo:
import java.util.HashSet;

//Node Class for data and next reference
class Node {
String data;
Node next;
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}

}
}
Node newNode = new Node();
newNode.setData(data);
} else {
while (temp.getNext() != null) {
temp = temp.next;
}
temp.next = newNode;
}
}
// method for explicit next reference to make loop
public void setNext(int n) {
while (temp1.next != null) {
temp1 = temp1.next;
}
for (int i = 1; i < n; i++) {
temp2 = temp2.next;
}
temp1.next = temp2;
}
}
public class MainClass {
public static void main(String[] args) {
// add 10 nodes where last node points(refers) to null
for (int i = 1; i <= 10; i++) {
}
// method changing the pointer(reference) of last node
// to a particular node to make it kind of circular
list.setNext(5);
// Use of hashset to find the intersection point
HashSet<Node> set = new HashSet<Node>();
while (temp.next != null) {
System.out.println(temp.data);
break;
}
temp = temp.next;
}
}
}
In the implementation class we have a additional function public void setNext(int n) which will make the last node of the singly linked list point to one of the node of the list.

Image 1: Debugging point before setNext method

Image 2: Debugging point after setNext method

Image 3: Linked List Structure before and after setNext method

We are using Hashset to find the intersection point.

Output:
a5

The output shows the intersceion point

Conclusion:
We have used hashset to find whether the element has been already added or not.