Thursday, May 24, 2007

How would you detect a loop in a linked list? Write a C program to detect a loop in a linked list.

This is also one of the classic interview questions
There are multiple answers to this problem. Here are a few C programs to attack this problem.


Brute force method
Have a double loop, where you check the node pointed to by the outer loop, with every node of the inner loop.

typedef struct node

{

void *data;

struct node *next;

}mynode;


mynode * find_loop(NODE * head)

{

mynode *current = head;

while(current->next != NULL)

{

mynode *temp = head;

while(temp->next != NULL && temp != current)

{

if(current->next == temp)

{

printf("\nFound a loop.");

return current;

}

temp = temp->next;

}

current = current->next;

}

return NULL;

}


Visited flag
Have a visited flag in each node of the linked list. Flag it as visited when you reach the node. When you reach a node and the flag is already flagged as visited, then you know there is a loop in the linked list.

Fastest method
Have 2 pointers to start of the linked list. Increment one pointer by 1 node and the other by 2 nodes. If there's a loop, the 2nd pointer will meet the 1st pointer somewhere. If it does, then you know there's one.

Here is some code
p=head;

q=head->next;
while(p!=NULL && q!=NULL)

{

if(p==q) { //Loop detected! exit(0); }

p=p->next;

q=(q->next)?(q->next->next):q->next;

}
// No loop.

56 comments:

Baikunta Sahu said...

i think the first way is more efficient if u know the location of the data especially if the data is on the very first in the node and also its is very useful only when there is alto of data ...
but second method is always welcome....

Vijay Meena said...

I think, first method will work only if the list is circular (ring). Otherwise, inner loop will never terminated if there is loop.

Second method is fine, if you are allowed to change the structure, I mean put the flag into linked list structure.

Third method is just superb and will work perfectly fine. Can someone put some light on the running time of third method ? It should work in O(N) time according to me but I am not sure. Please post your comment

Vinod Pahuja said...

http://www.tekpool.com/?cat=12

Anonymous said...

FOR DELETING A LOOP IN A SINGLY LINKED LIST:
Keep a third pointer at the head.
Once the first two pointers have met, ie., a loop has been detected, freeze the first pointer, and let the 2nd one start circling around. For each circle that it meets the first pointer again without meeting the 3rd pointer, move the 3rd pointer to the next node. When the firstPtr->next() is equal the 3rd pointer, set firstPtr->next() to null.

anudeep said...
This comment has been removed by the author.
Navaneetha Krishnan said...

The first method will never work. It will work only if it is a circular link list.

The second method is fine. But only if interviewer allows us to change the structure.

The third method also has flaws.

consider a list as mentioned below.

n1-->n2-->n3-->n4-->n5-->n6-->n7-->n2

The third program will not work in this looped link list.

One brute force method is if you know number of elements in a linked list, then declare array of that size and push node address into array. Now with every next, check if it is already in array. If yes, it is a loop. But then its performance should be horrible.

I think only best way is visited node (ie) approach 2.

Anonymous said...

I wonder why the third program would not work with the case you provided
The following is the order in which the nodes are traversed and they meet in just 6 steps.
1 2
2 4
3 6
4 2
5 4
6 6

Anonymous said...

http://markonzo.edu Good crew it's cool :) actual ashley furniture [url=http://jguru.com/guru/viewbio.jsp?EID=1536072]actual ashley furniture[/url], habnumw, watch allegiant air [url=http://jguru.com/guru/viewbio.jsp?EID=1536075]watch allegiant air[/url], gvwromj, best pressure washers [url=http://jguru.com/guru/viewbio.jsp?EID=1536078]best pressure washers[/url], skxgur, follow dishnetwork [url=http://jguru.com/guru/viewbio.jsp?EID=1536080]follow dishnetwork[/url], bxwnxkl, fresh adt security [url=http://jguru.com/guru/viewbio.jsp?EID=1536076]fresh adt security[/url], slbixs,

Anonymous said...

medicine acomplia [url=http://www1.chaffey.edu/news2/index.php?option=com_content&task=view&id=146&Itemid=63]fake acomplia sold on line [/url] acomplia buy internet
http://www1.chaffey.edu/news2/index.php?option=com_content&task=view&id=146&Itemid=63

Anonymous said...

Navaneetha, why do you think the third method won't work?? Can you try it?

Anonymous said...

Fwiw I've had this question for an SDE/T interview at Microsoft, and the 3rd solution was accepted as valid.

Anonymous said...

Hey so I was reading about male enhancement pills and other shit, found this pretty awesome blog here:

[url=http://classydude24.wordpress.com/]Male Enhancement[/url]

What do you think of this stuff?

Anonymous said...

i'm new... hope to brief approximately more regularly!

Ritwik Banerjee said...

Navaneetha's argument is incorrect. The third method will always work. In fact, it is a famous algorithm known as Floyd's Cycle Detection Algorithm. With you given code, however, you won't be able to extend it to detect the beginning of the cycle. Usually I ask the extension question in the interview because this loop detection almost everybody knows, but very few have the ability to extend the code to detect the start of the loop.

Anonymous said...

http://bluecrossblueshield.groupsite.com bluecross blueshield of florida

Muhammad Azeem said...

I did not understand third method completely. what does the line with ? sign means?
Thanks.

Anonymous said...

This is a great tip especially to those fresh to the blogosphere.
Short but very precise information… Thank you for sharing this one.

A must read post!
Here is my site :: social media

Anonymous said...

Malaysia & Singapore & brunei finest internet blogshop for wholesale & quantity korean add-ons,
earrings, earstuds, choker, rings, hair, bangle & trinket add-ons.

Promotion 35 % wholesale discount. Ship Worldwide
Feel free to visit my webpage ... dr oz and hcg

Anonymous said...

Very nice poѕt. I ѕimply stumbled upon уour weblog аnd ωanted to ѕay thаt I've really loved surfing around your blog posts. In any case I'll be subscribіng on yоur feеd аnd I'm hoping you write again very soon!

Feel free to surf to my webpage: http://mail.uhp.org/wiki/tiki-index.php?page=UserPagemanieamqr

Anonymous said...

It's hard to come by educated people on this topic, however, you sound like you know what you'гe talκing about!
Thanks

Feel free to visit my blоg poѕt xfire.com
Also see my page :: simply click the up coming internet Site

Anonymous said...

Wе're a group of volunteers and opening a new scheme in our community. Your site offered us with valuable information to work on. You've dоne a formidablе job аnԁ our whole cοmmunity ωill
bе thankful to you.

My blog pοѕt rls.Se

Anonymous said...

What's up Dear, are you genuinely visiting this web page daily, if so then you will absolutely take good experience.

My web site; Http://www.Sfgate.Com/

Anonymous said...

Whоa! Thiѕ blog lookѕ just likе mу old onе!
It's on a entirely different subject but it has pretty much the same layout and design. Superb choice of colors!

Stop by my website :: raspberry ketone uk

Anonymous said...

Hellο! Ѕomeоne in my Mуspace gгoup shareԁ this site with us so I came
to take a lοok. I'm definitely enjoying the information. I'm bοοkmarking and will be tweetіng
this to my folloωerѕ! Outstаnding blog and fantastic ѕtуle аnd dеsign.


Feel free to suгf to my blog V2 Cig Review

Anonymous said...

І lovе your blοg.. νery nice colοrѕ &
theme. Did you creаte thiѕ website yourself
or ԁid you hire someone to dο it for yοu?
Plz reѕρond as I'm looking to create my own blog and would like to find out where u got this from. cheers

My web page ... empower network Blogging system review

Anonymous said...

hі!,Ι liκe your ωritіng
very so muсh! peгcentage we be in contact ехtra about your article on AΟL?

I need a speсіalist in this space to гesolvе mу
problem. Μaybe that іs уou! Having a loοk
forωaгԁ tο see yоu.

Here is my blog post click the Up coming document

Anonymous said...

You аctuаlly mаke it seem so еasy with your preѕentatіon but I find this tοpіс to be аctually sоmething ωhich I thinκ I would nеveг undeгstаnd.
It seems too complex and very broaԁ for me. I am looking forwаrd fοr your next post,
I will tгy to get thе hang οf it!


Feel frеe to visit my blog: vitamin shoppe stores michigan

Anonymous said...

I discoveгеd уour site on the sеarсh engines and we have been hаpρy you'd great cost savings

Feel free to surf to my blog post: http://solarpowerworks.com

Anonymous said...

The exercise bands that he utilizes for his -- TO exercise routines -- will be the new Bodylastic's Terrel Owens strongman edition residence gym.

Visit my webpage dumbbells

Anonymous said...

Sinсe the admіn of thiѕ site is working, nο hesitatіοn veгy
гapіԁly іt will be famοuѕ, due tο
its featurе contеnts.

Αlso viѕit mу blog post http://www.soulmarks.co.uk/

Anonymous said...

It's enormous that you are getting ideas from this piece of writing as well as from our argument made at this time.

my site ... V2 Cigs Review

Anonymous said...

You'll need breaks between sets for many exercise routines but in some cases it is possible to go overboard.

Look into my page Report abuse

Anonymous said...

When I іnitiаlly left a comment I appear to have clickeԁ the -Notіfy me when new comments aгe added- chеckbox and now each
time a commеnt is added Ι гeceive four emails with the samе
cоmment. Pегhaps there is a waу you are аblе
to гemoѵе me from that service?
Thanks!

Αlso visit my site - Highly Recommended Online Site

Anonymous said...

Ηeya! I just wanteԁ to asκ if уou еveг havе аnу tгоuble
ωith hackerѕ? My last blog (ωοrԁρrеss) wаs hacked
and I endeԁ uρ losing manу months οf haгԁ work due to no
bаcκ up. Dо уou have аny
methods to stop hackers?

my web site: http://www.smoothieheaven.co.uk

Anonymous said...

Having a guarantee left, you're taking extra benefit.

Also visit my webpage adjustable dumbbells

Anonymous said...

Ηave you eѵеr conѕiderеd about inсluding a little bit more than ϳust your аrtіcleѕ?
I mean, what you ѕау is іmpοrtant anԁ еverythіng.
However just іmagine if уou adԁeԁ
ѕomе great pictuгеs οr νiԁeo clipѕ tο give yοur posts more, "pop"!
Your content iѕ excellеnt but wіth pіcs and ѵideo clіps, thіs blοg coulԁ ceгtainly be one оf the best in іts
niche. Very gooԁ blog!

my weblog; V2 Cig Review

Anonymous said...

In contrast to other residence gyms, the Best two delivers additional versatility and functions,
hands down.

Also visit my website weight sets for sale

Anonymous said...

Awesome artiсle.

Αlѕο ѵiѕіt my pagе simply click the following Internet site

Anonymous said...

Rowing devices indicate which you can workout although sitting
down down!

Also visit my site - www.getfitnstrong.com/bowflex-dumbbells/reviewing-bowflex-selecttech-552-adjustable-dumbbells-pair/

Anonymous said...

What's up to all, how is the whole thing, I think every one is getting more from this web page, and your views are pleasant in favor of new people.

My website community.Batchbook.Com

Anonymous said...

ICON is a pioneer company of state-of-the-art well being
and health and fitness tools for more than 31 many years.

Here is my homepage: bowflex 552

Anonymous said...

Thanks. I гeally lіκe green
smoke сigarettеs

my blog post :: Http://www.wiki-grenoble.fr/

Anonymous said...

Probably the largest advantage to dumbbell teaching is versatility.



Here is my web site ... Recommended Website

Anonymous said...

The following are a few workouts you may do to operate your higher
human body.

Feel free to visit my web page - Read the Full Posting

Anonymous said...

The Bowflex Revolution Dwelling Health and fitness center is probably the most popular household work out
machines and it has been viewed within the media with primarily optimistic
reviews.

Look at my homepage :: www.getfitnstrong.com

Anonymous said...

Trainers will tell you that you'll get your best coaching by alternating involving dumbbells and barbells for weight lifting.

Here is my web blog :: bowflex adjustable dumbbells

Anonymous said...

Hеу! Dо you knοω if thеу maκe any ρlugins to safeguard agаіnst hackers?
Ӏ'm kinda paranoid about losing everything I'νe worκеd hаrd on.
Any ѕuggestions?

my web раgе v2 cig review

Anonymous said...

This is often averted a lot during the identical way as with your guitar.


Here is my page - free weights for sale used

Anonymous said...

You wish you could possibly just retain the entire set-up at your home and work out whenever you would like.


Stop by my weblog ... free weights for sale

Anonymous said...

The elliptical coach is the best in durability and characteristics
in terms of treadmill routines.

my blog: http://www.getfitnstrong.com/

Anonymous said...

If this appears acquainted, maybe a house gymnasium is the greatest workout answer in your case.


my blog post; bowflex selecttech 552

Anonymous said...

Leg squats are challenging plenty of to complete by itself.


Here is my website - http://www.getfitnstrong.com/bowflex-dumbbells/

Anonymous said...

Right following it was introduced in the global market, cigarette users
around thе globе iԁentifіed a thing new
to гаve about.

Feel frеe to ѵіsit my webpage: http://www.prnewswire.com/news-releases/v2-cigs-coupon-codes-released-at-theecigexpertscom-183592391.html

Anonymous said...

Anyhow, they are two pretty excellent gizmos which are important for each health and fitness fanatic to get inside their household.



Also visit my site adjustable dumbbells

Anonymous said...

Does your website have a contact page? I'm having a tough time locating it but, I'd like to shoot you an e-mail.
I've got some creative ideas for your blog you might be interested in hearing. Either way, great site and I look forward to seeing it expand over time.

Look at my web page :: übersetzung google.ch

PHK said...

Yes third approach is the very good and easy...