Note 1

Take Note:

Take a note while surfing.

Note With Ink

Give your Note a Colorful Tag.

Easy to Access

Stay on same information and in Sync wherever you are.

Note 2

Take Note:

Organize your information,It may take Shape.

Think With Ink

Differ your Content by Color.

Easy to Access

Easy to pull up your content from anywhere anytime.

Note 3

Take Note:

Don't Let information to miss,Because it take shape

Note With Ink

Simple an Easy Way to take a note.

Easy to Access

Get the same in next visit.

Please wait...

Program Discussion :: Linked List
Home > Programs > Linked List

29. Write an efficient program to detect and remove loop in a linked list



/* Link list node */
struct Node
    int data;
    struct Node* next;

/* Function to remove loop. Used by detectAndRemoveLoop() */
void removeLoop(struct Node *, struct Node *);

int detectAndRemoveLoop(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)
            removeLoop(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 remove loop.
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)

    /* If ptr2 did't reach ptr1 then try the next node after ptr1 */
    ptr1 = ptr1->next;

/* After the end of loop ptr2 is the last node of the loop. So
    make next of ptr2 as NULL */
ptr2->next = NULL;

/* Function to print linked list */
void printList(struct Node *node)
    while (node != NULL)
        printf("%d ", node->data);
        node = node->next;

struct Node *newNode(int key)
    struct Node *temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = key;
    temp->next = NULL;
    return temp;

/* Drier program to test above function*/
int main()
    struct Node *head = newNode(50);
    head->next = newNode(20);
    head->next->next = newNode(15);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(10);

    /* Create a loop for testing */
    head->next->next->next->next->next = head->next->next;


    printf("Linked List after removing loop \n");
    return 0;

Asked In ::

Post Your Answer Here:

Name *


Post Your Reply Here: