1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Loop in single linked list

Discussion in 'C' started by mr.anandc, May 6, 2008.

  1. mr.anandc

    mr.anandc New Member

    Joined:
    May 6, 2008
    Messages:
    18
    Likes Received:
    0
    Trophy Points:
    0
    How to find a loop in a single linked list? The loop can be to any node in the list i.e., last node of the list can loop back to any existing node in the list.

    Thanks.
     
  2. asadullah.ansari

    asadullah.ansari TechCake

    Joined:
    Jan 9, 2008
    Messages:
    356
    Likes Received:
    14
    Trophy Points:
    0
    Occupation:
    Developer
    Location:
    NOIDA
    Take two pointer one pointing to head and increment it by one by one. and second pointer also point to head and increment it by two and check these two pointer for eqaulity. If equal then loop is there .
     
  3. mr.anandc

    mr.anandc New Member

    Joined:
    May 6, 2008
    Messages:
    18
    Likes Received:
    0
    Trophy Points:
    0
    Thanks for the reply.

    I haven't got the concept. Suppose if I have a linked list of 10 nodes and last node is pointing back to second node, how this procedure will find a loop.

    Thanks.
     
  4. asadullah.ansari

    asadullah.ansari TechCake

    Joined:
    Jan 9, 2008
    Messages:
    356
    Likes Received:
    14
    Trophy Points:
    0
    Occupation:
    Developer
    Location:
    NOIDA
    Code:
    Node *Isloop(Node *List)
    {
      Node *ptr1=List, *ptr2=List,*ptr=NULL;
      while( (ptr1!=NULL) && (ptr2!=NULL))
      {
        if (ptr && (ptr1 == ptr2))
        {
          return ptr;
        }
        ptr = ptr1;
        ptr1=ptr1->next;
        ptr2=ptr2->next;
        if (ptr2)
        {
          ptr2=ptr2->next;
        }
      }
    }
    
     
  5. mr.anandc

    mr.anandc New Member

    Joined:
    May 6, 2008
    Messages:
    18
    Likes Received:
    0
    Trophy Points:
    0
    Thanks for the code.

    Can please explain behavior of this for the above scenario I mentioned like, 10 nodes in the list and last node pointing back to 2nd node. In this case how the code will find the loop.
     
  6. asadullah.ansari

    asadullah.ansari TechCake

    Joined:
    Jan 9, 2008
    Messages:
    356
    Likes Received:
    14
    Trophy Points:
    0
    Occupation:
    Developer
    Location:
    NOIDA
    ptr1 1 2 3 4 5 6 7 8 9 10
    ptr2 1 3 5 7 9 2 4 6 8 10

    So loop is there bcoz ptr1==ptr2.
    Here 1 2 3 etc represent node1 node2 node3 etc

    Now I think you can understand. If Any doubt ask me?
     
  7. mr.anandc

    mr.anandc New Member

    Joined:
    May 6, 2008
    Messages:
    18
    Likes Received:
    0
    Trophy Points:
    0
    Great logic, now I understood. Thanks a lot.
     

Share This Page