Welcome,
%1$s
. Please
login
or
register
.
October 18, 2017, 06:32:43 PM
Submit
Quotes
CELL TRACKER
Online Fun Database

Interview Questions

C Questions

Loop inside a linked list
Random
Celebrities
Places
Humour
Quotes
Informative
Articles
Stories
Indian
Videos
Puzzles
Easy
Medium
Tough
On Maths and Physics
What am I?
Puzzled PJs
« previous
next »
:
1
: Loop inside a linked list ( 3059 )
Loop inside a linked list
«
:
May 12, 2007, 12:15:58 AM From
Shrinidhi
»
Loop inside a linked list
Given a single linked list, write a program/algorithm to find whether there exists any loop. (Without using any extra memory of O(n))
Liked It? Share it!
Tweet
Re: Loop inside a linked list
«
#1 :
May 12, 2007, 12:17:26 AM From
Shrinidhi
»
1. Keep 2 pointers. Say p and q.
2. Make p & q both point the head of the list.
3. Move p by one node and q by 2 nodes.
4. Repeat step 3 until
a. Either q points to NULL. In this case there is no loop.
b. Or Both p & q meet each other again. In this case there is loop.
Re: Loop inside a linked list
«
#2 :
May 12, 2007, 12:18:28 AM From
Shrinidhi
»
int isLoop(Node *head)
{
Node *p=head;
Node *q=head>next;
while(p!=NULL && q!=NULL)
{
if(p==q)
{
return 1; //Loop Exists. Hence return success
}
p=p>next;
q=(q>next)?(q>next>next):q>next;
}
return 0; //There is no loop
}
Re: Loop inside a linked list
«
#3 :
May 18, 2007, 11:29:28 PM From
Prateek
»
I was asked in Cisco interview to calculate the worst case and best case time complexity for finding whether there exists a loop.
Can anyone tell me what they are?
Re: Loop inside a linked list
«
#4 :
May 19, 2007, 12:18:54 AM From
Poonam
»
Node1 > Node2 > Node3 > Node4 > Node5 > Node6 > Node7 > Node8 > Node5
This linked list is looping from 8 back to 5. There are 4 nodes before the loop and 4 nodes inside. In this linked list and in the algo as explained by shrinidhi the loop is detected as soon as the pointer p moves to node5 for the first time. And there cannot be any other best scenario possible...
Hence the best case time complexity is node
k+1
where k is the number of nodes outside the loop.
Re: Loop inside a linked list
«
#5 :
May 19, 2007, 11:26:12 AM From
Ria
»
Yeah I agree with Guru... O(k+1) is the best case time taken if there exist a loop.
However if there aren't any loop in the linked list it will be found in just n/2 steps, where n is the number of nodes in the list.
:
1
« previous
next »
Best Rated
List All>>
Latest
Random
Loading...