Find if a singly linked List has loop or not. How to find out middle element from a looped single linked list
3 posters
Page 1 of 1
Find if a singly linked List has loop or not. How to find out middle element from a looped single linked list
public boolean findloop(LinkedListNode head){
LinkedListNode n1=head;
LinkedListNode n2=head;
n1=n1.next;
n2=n2.next.next;
while(n2!=null){
if(n1==n2)
break;
n1=n1.next;
n2=n2.next.next;
}
if(n2==null)
return false;
return true;
}
LinkedListNode n1=head;
LinkedListNode n2=head;
n1=n1.next;
n2=n2.next.next;
while(n2!=null){
if(n1==n2)
break;
n1=n1.next;
n2=n2.next.next;
}
if(n2==null)
return false;
return true;
}
Re: Find if a singly linked List has loop or not. How to find out middle element from a looped single linked list
The program will fail in multiple situations, for example, what if linked list had odd number of nodes? What if it has only one nodes? I have found out that the interviewers are always very concerned about these corner cases. I often forgot to address it, it's better we begin to pay attention now.
viterbi- Posts : 32
Join date : 2011-09-03
Re: Find if a singly linked List has loop or not. How to find out middle element from a looped single linked list
ListNode FindBeginning(ListNode head){
ListNode n1=head;
ListNode n2=head;
//Find meeting point
while(n2.next!=null){
n1=n1.next;
n2=n2.next.next;
if(n1==n2){
break;
}
}
if(n2.next==null)
return null;
n1=head;
while(n1!=n2){
n1=n1.next;
n2=n2.next;
}
return n2;
}
ListNode n1=head;
ListNode n2=head;
//Find meeting point
while(n2.next!=null){
n1=n1.next;
n2=n2.next.next;
if(n1==n2){
break;
}
}
if(n2.next==null)
return null;
n1=head;
while(n1!=n2){
n1=n1.next;
n2=n2.next;
}
return n2;
}
skyboard- Posts : 31
Join date : 2011-09-03
Similar topics
» Combine two sorted linked list
» Convert any BST into doubly linked list in place
» Revert a linked list with a cycle in it. (Thus removing the cycle)
» Insert in front of the list
» Deleting Elements from List
» Convert any BST into doubly linked list in place
» Revert a linked list with a cycle in it. (Thus removing the cycle)
» Insert in front of the list
» Deleting Elements from List
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
|
|