,

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:
package com.linkedlist;
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;
}
}

// Singly linked list implementation
class SinglyLinkedList {
Node head;
public Node getHead() {
return head;
}
public void setHead(Node head) {
this.head = head;
}
// add Node
public void add(String data) {
Node newNode = new Node();
newNode.setData(data);
if (head == null) {
head = newNode;
} else {
Node temp = head;
while (temp.getNext() != null) {
temp = temp.next;
}
temp.next = newNode;
}
}
// method for explicit next reference to make loop
public void setNext(int n) {
Node temp1 = head;
Node temp2 = head;
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) {
// create singly linked list
SinglyLinkedList list = new SinglyLinkedList();
// add 10 nodes where last node points(refers) to null
for (int i = 1; i <= 10; i++) {
list.add("a" + 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>();
Node temp = list.head;
while (temp.next != null) {
if (!set.add(temp)) {
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.

No comments:

Post a comment