Hi All,
Find below the function to detect a loop in a linked list and the point from
where loop occurs.
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct node
{
int data;
struct node* next;
};
/* Function to remove loop. Used by detectAndRemoveLoop() */
void LoopPoint(struct node *, struct node *);
/* This function detects and removes loop in the list
If loop was there in the list then it returns 1,
otherwise returns 0 */
int detectLoop(struct node *list)
{
struct node *slow_p = list, *fast_p = list;
while (slow_p && fast_p && fast_p->next)
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;
/* If slow_p and fast_p meet at some point then there
is a loop */
if (slow_p == fast_p)
{
LoopPoint(slow_p, list);
/* Return 1 to indicate that loop is found */
return 1;
}
}
/* Return 0 to indeciate that ther is no loop*/
return 0;
}
/* Function to find loop point.
loop_node --> Pointer to one of the loop nodes
head --> Pointer to the start node of the linked list */
void removeLoop(struct node *loop_node, struct node *head)
{
struct node *ptr1;
struct node *ptr2;
/* Set a pointer to the beging of the Linked List and
move it one by one to find the first node which is
part of the Linked List */
ptr1 = head;
while(1)
{
/* Now start a pointer from loop_node and check if it ever
reaches ptr2 */
ptr2 = loop_node;
while(ptr2->next != loop_node && ptr2->next != ptr1)
{
ptr2 = ptr2->next;
}
/* If ptr2 reahced ptr1 then there is a loop. So break the
loop */
if(ptr2->next == ptr1)
break;
/* If ptr2 did't reach ptr1 then try the next node after ptr1 */
else
ptr1 = ptr1->next;
}
/* ptr1->data is a point where loop occurs.*/
/* to remove loop*/
ptr2->next=NULL
}
On Thu, Sep 1, 2011 at 9:12 AM, Don <[email protected]> wrote:
> @Rahul
> The problem is to determine if there is a loop. That means there might
> not be. And if there isn't, you really shouldn't dump core.
> Don
>
> On Aug 31, 10:17 pm, Siddhartha Banerjee <[email protected]>
> wrote:
> > how can head2->next be null in a linked list witha loop???
> > i mean it would just go around in circles right???
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Regards :
ROHIT JALAN
B.E. Graduate,
Computer Science Department,
RVCE, Bangalore
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
