Results 1 to 8 of 8

Thread: Circle in linked list

  1. #1
    Geek_Guest
    Guest

    Circle in linked list

    Question asked by visitor manish jaiswal

    What is the procedure to be applied for finding whether there is any circle formed in a linked list?

    plz keep in mind there is a bulk of elements in linked list, so complexity must be negligible.


  2. #2
    Expert Member
    Join Date
    Nov 2006
    Answers
    518

    Re: Circle in linked list

    In a doubly linked list,

    if ‘tail.next’ is equal to ‘head’

    or

    ‘head.previous’ is equal to ‘tail’

    then it is a circular linked list.

    Lack of WILL POWER has caused more failure than
    lack of INTELLIGENCE or ABILITY.

    -sutnarcha-

  3. #3
    Junior Member
    Join Date
    Mar 2009
    Answers
    2

    Re: Circle in linked list

    basic concept is that if a particular node is linked to any of the previous nodes,then it forms a circle.
    even a single node with a link pointing to itself is a circle length one.

    thus by checking whether the link field of the last node is linked to the header node , you can find whether a circle is present or not.


  4. #4
    Junior Member
    Join Date
    Mar 2010
    Answers
    1

    Re: Circle in linked list

    the logic is quite simple...if the last node points to the head node,then its a circular link list. eg:

    struct node*checkcirlinklist(struct node*head)
    {
    struct node *p;
    p=head;
    while(p!=NULL)
    {
    if(p->next==head)
    {
    printf("its a circular link list");
    break;
    }
    else
    p=p->next;
    }
    if(p==NULL)
    printf("its not a circular link list");


    }

    Last edited by avanish_2k; 03-29-2010 at 09:30 AM.

  5. #5
    Junior Member
    Join Date
    Feb 2010
    Answers
    18

    Re: Circle in linked list

    You can have two pointers p,q pointing to the header node...Inside a while loop you move the second pointer by two nodes and first pointer by one node...if loop exists,definitely the two pointers will meet each other,so p==q condition gets satisfied...This method not only finds the loop formed in the header node but also finds the loop formed in any other nodes...The code as follows:-

    {
    struct node *p=header;
    struct node *q=header;
    int k=0;
    while(q->next!=null && !k)
    {
    p=p->next;
    q=q-next->next;
    if(p==q)
    k=1;
    }
    if(k)
    printf("loop exists")
    else
    printf("no loop");
    }

    if there is no loop then q will reach null before p...If there is no loop,the loop will set k as 1 at one time,I think this will work for all...


    regards,
    rms...


  6. #6
    Junior Member
    Join Date
    Jan 2009
    Answers
    1

    Question Function Recursion

    I know in c / c++, a function(module) called by itself more than once is called function recursion. But i want to know the actual process i.e how data is executing inside and how display occur by giving any authentic example.. Thanx


  7. #7
    Junior Member
    Join Date
    Apr 2008
    Answers
    13

    Re: Circle in linked list

    For recursive function calls, every time the function is called, it get loaded onto STACK. Consider the below example code for finding factorial of a number using recursion.
    /*****************/
    int main(int argc, char* argv[])
    {
    int num = 5;

    printf("Factorial!! = %d\n", fact(num));

    return 0;
    }

    int fact(int num)
    {
    if((num == 1) || (num == 1))
    {
    return 1;
    }
    else
    {
    return (num * fact(num-1));
    }
    }
    /**********************/

    Below is the CALL STACK for factorial of number 5
    /*********************/
    2 * fact(int 1) line 21
    3 * fact(int 2) line 25 + 12 bytes
    4 * fact(int 3) line 25 + 12 bytes
    5 * fact(int 4) line 25 + 12 bytes
    fact(int 5) line 25 + 12 bytes
    main(int 1, char * * 0x00910e80) line 12 + 9 bytes
    /*********************/

    Explaination: The evaluation shall be as per the stack behaviour(LIFO). For the 1st time when fact(num) is called, it will be loaded in stack. inside this function fact(num-1) is called as long as the else condition is satisfied. When num = 1 or num = 0 is satisfied, then evaluation starts and evaluation order will as shown above. Return Value from each stage is multiplied with previous stage and FINALLY returns to the MAIN function where factorial value is displayed.

    Hope this is useful!!!!
    --> Pavan Mustyala


  8. #8
    Junior Member
    Join Date
    Apr 2008
    Answers
    13

    Re: Circle in linked list

    Hi, This below code can be used to check for circle in the list. This is updated version for RMSECE's post. The number of iterations will reduce by 1 compared to that code since initially, 1st pointer points to HEAD node and 2nd pointer points to node next to HEAD. There by one iteration is reduced here. But in worst case, both methods results in same number of iterations.

    void findCircleInList(LIST *pHead)
    {
    LIST *p = pHead;
    LIST *q = pHead->pNext;
    int k = 0;
    int count = 0;

    while(q != NULL && q->pNext!= NULL && !k)
    {
    p = p->pNext;
    q = q->pNext->pNext;
    if(p == q)
    k = 1;
    count++;
    }
    if(k)
    printf("\n\nloop exists % d\n\n", count);
    else
    printf("\n\nno loop %d\n\n", count);
    }


Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
About us
Applying for a job can be a stressful and frustrating experience, especially for someone who has never done it before. Considering that you are competing for the position with a at least a dozen other applicants, it is imperative that you thoroughly prepare for the job interview, in order to stand a good chance of getting hired. That's where GeekInterview can help.
Interact