Detecting a loop in single linked list
Related Blog Items
- Detecting broken links in double linked list
- Reversing a circular single linked list using pointers
- Reversing a single linked list using stack
- Reversing single linked list recursively
- Circular Doubly Linked List With Out Using Special Head or Tail Node
Please refer this post for linked list basics and all other operations on linked lists.
Loops in linked list can be detected by inserting dummy nodes after every node, so if we find dummy node after a node already, that says that list has a loop. The diagram below explains this. This method takes O(n) time and O(n) additional space.
Loops in linked list can also be detected by running two loops paralally, one loop traverse list by one node, another loop traverse list by skipping a node while going to next node. this way they meet at some point of time, if the list has a loop. The diagram below explains this. This method takes O(n) time in best case.
program for finding loop by traversing with two pointers… this program takes input as linked list, returns a node(where a loop starts), or returns NULL if we could not find a loop…
Node *detectloop(Node *list) { Node *n1, *n2; //prev indicates loop started at this point Node *prev=NULL; for(n1=list, n2=list; (n1!=NULL) && (n2!=NULL); ) { if (prev && (n1 == n2)) { return prev; } prev = n1; n1=n1->next; n2=n2->next; if (n2) { n2=n2->next; } } }
comments?
Popularity: 23%
You need to log on to convert this article into PDF
Related Blog Items - Detecting broken links in double linked list
- Reversing a circular single linked list using pointers
- Reversing a single linked list using stack
- Reversing single linked list recursively
- Circular Doubly Linked List With Out Using Special Head or Tail Node
Related Blog Items
- Detecting broken links in double linked list
- Reversing a circular single linked list using pointers
- Reversing a single linked list using stack
- Reversing single linked list recursively
- Circular Doubly Linked List With Out Using Special Head or Tail Node
Can we not just run a loop checking for where the next is pointing?
so long as it finds a new address there is no loop.
April 26th, 2007 at 2:02 am
how can we say the next is address is new address?, again we need to look back at our old traversed nodes to find out whether it is a new address or old address, for doing this it will cost us O(n2).
April 26th, 2007 at 1:09 pm
ohh okay, but i have a small question,
the address that a pointer shows, is it the true location or just a relative indicator?
May 1st, 2007 at 11:23 am
As the nodes will be malloc’ed, so we are going to get memory from heap, so it is a true location, all nodes will have different addresses (and there is no way they are related)…
May 2nd, 2007 at 5:59 pm
I think we need to increment the pointer to the node ‘n2′ one more time in the for loop of the algorithm to find the loop in the list.With the present implemention, for loop in the algorithm will never terminate on trying to detect the loop,when a loop is present(because no pointer will be equal to NULL on incrementing because of the loop).Anyways, to fix the problem I feel we must do the following correction in the for loop:
if(n2 && (n2->next)){
n2 = ((n2->next)->next);
}
else{
// no loop found
return;
}
May 25th, 2007 at 10:13 pm
pratap, there is no issue in the algorithm, it terminates when list has loop because n1 == n2, and that is the start of the loop so it returns from that location. In fact the only difference from your mentioned piece of code and the listed code is listed code moves 2nd pinter at +1, your code moves 2nd pointer at +2 speed.
January 22nd, 2008 at 11:02 pm
o(n) doesnt look good, specially because its modifying the original list, i’d rather hash the addresses into an N element hash list with open addressing, it uses less space too(no links sweetie). and is easy to keep track of(no linking either sunshine), just a random thought thou.
March 13th, 2008 at 9:53 am