By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,996 Members | 896 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,996 IT Pros & Developers. It's quick & easy.

loop in a linked list

P: 6
Q: Plz send me the code for this question.

How to check whether there exists any loop in a linked list. thanks.
regards
sanjay
Jun 17 '07 #1
Share this Question
Share on Google+
3 Replies


weaknessforcats
Expert Mod 5K+
P: 9,197
Traverse the linked list and keep the addresses of each node in a table sorted by address. If the address of a next node is already in the table, you have a loop.

I assume you are using C.

In C++ you use the list template which does not have these problems.
Jun 18 '07 #2

Expert 10K+
P: 11,448
Traverse the linked list and keep the addresses of each node in a table sorted by address. If the address of a next node is already in the table, you have a loop.
There's a nice trick that doesn't need any table: imagine two ants running over
your list; one of them runs twice as fast as the other; when they meet again
during the run there's a loop in the list.

kind regards,

Jos
Jun 18 '07 #3

weaknessforcats
Expert Mod 5K+
P: 9,197
There's a nice trick that doesn't need any table: imagine two ants running over
your list; one of them runs twice as fast as the other; when they meet again
during the run there's a loop in the list.
Always a slick solution. I haven't heard about this one.
Jun 18 '07 #4

Post your reply

Sign in to post your reply or Sign up for a free account.