JIGYASA

An online placement forum.


You are not connected. Please login or register

@ Linked List

Go down  Message [Page 1 of 1]

1 @ Linked List on Sun Mar 07, 2010 4:23 am

Lucifer


Admin
Given a linked list, find whether it has a loop or not.

View user profile http://jigyasa.forumn.org

2 Re: @ Linked List on Sat Mar 13, 2010 2:30 am

Clarification: do we know the number of nodes in the linked list?

If yes: Lets say it has n nodes. An O(n) solution is traverse the list seeking the next node every time for n-1 times. If, the "next" pointer now points to NULL, then the linked doesn't have a cycle, else it has one Smile.

Is there some thing smarter?

View user profile

3 @indranil on Sat Mar 13, 2010 10:42 pm

Lucifer


Admin
No, the no. of nodes is not given....ya, there is something smarter. Wink

View user profile http://jigyasa.forumn.org

4 Re: @ Linked List on Tue Mar 23, 2010 8:18 am

I hope you are not trying to tag/id visited nodes!

View user profile

5 @indranil on Tue Mar 23, 2010 3:58 pm

Lucifer


Admin
no tagging is needed.. think in terms of relative velocity Smile ...

View user profile http://jigyasa.forumn.org

6 @everyone on Wed Apr 07, 2010 4:14 am

Lucifer


Admin
any ideas...

View user profile http://jigyasa.forumn.org

7 Re: @ Linked List on Tue Sep 21, 2010 6:22 am

Lucifer


Admin
Take 2 pointers.. p1 and p2...

make p1 traverse the list at the rate of one node / cycle
and p2 traverse the list at the rate of 2 nodes / cycle.

If p1 and p2 match then there is a loop , otherwise not.. make sure you check for NULL (termination condition)

say head of the list is root.

bool loop = FALSE;
p1 = p2 = root;

while ( p1 && p2->next)
{

p1 = p1->next;
p2 = p2->next->next;

if (p1 == p2)
{
loop = TRUE;
break;
}

}

View user profile http://jigyasa.forumn.org

Sponsored content


Back to top  Message [Page 1 of 1]

Permissions in this forum:
You cannot reply to topics in this forum