import java.util.HashSet;
class LinkList3{
Node head;
Node sl;
Node ft;
class Node{
int data;
Node next;
public Node(int data,boolean flag, Node node){
this.data=data;
this.next=null;
}
@Override
public String toString() {
return "{"+this.data+"}";
}
}
public Node push(int data,boolean flag, Node node){
Node link=new Node(data,flag,node);
if(head==null){
head=link;
}else{
Node current=head;
while(current.next!=null){
current=current.next;
}
if(flag && node!=null){
link.next=node;
}
current.next=link;
}
return link;
}
public void display(){
Node current=head;
while(current!=null){
System.out.print(current);
current=current.next;
}
}
public boolean detectLoop1(){
HashSet set=new HashSet();
Node current=head;
boolean flag=false;
while(current.next!=null){
if(set.contains(current)){
flag=true;
break;
}
set.add(current);
current=current.next;
}
return flag;
}
public boolean detectLoop2(){
sl=head;
ft=head.next;
while(sl!=ft){
if(ft==null || ft.next==null){
return false;
}
sl=sl.next;
ft=ft.next.next;
}
return true;
}
public boolean removeLoop1(){
HashSet set=new HashSet();
Node previous=head;
Node current=head;
while(current!=null){
if(set.contains(current)){
previous.next=null;
return true;
}
set.add(current);
previous=current;
current=current.next;
}
return false;
}
public void removeLoop2(){
ft=head;
while(ft!=null){
Node ptr=sl;
while(ptr.next!=sl && ptr.next!=ft){
ptr=ptr.next;
}
if(ptr.next==ft){
ptr.next=null;
return;
}
ft=ft.next;
}
}
}
public class DetectLoop2 {
public static void main(String[] args) {
LinkList3 linkList3=new LinkList3();
linkList3.push(10,false,null);
LinkList3.Node push = linkList3.push(20, false, null);
linkList3.push(30,false,null);
linkList3.push(40,false,null);
linkList3.push(50,true,push);
boolean flag=false;
//linkList3.display();
// flag= linkList3.detectLoop1();
flag= linkList3.detectLoop2();
if(flag){
System.out.println("loop found");
}else{
System.out.println("loop not found");
}
//linkList3.removeLoop1();
linkList3.removeLoop2();
linkList3.display();
}
}
TechInsiderStory is place where you can find basic knowledge of various technology and framework. TechInsiderStory is provide free knowledge on various technology and framework.
Detect And Remove Loop from LinkList
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment