Data Structure/Algorithm Challenger I

We have a singly-linked-list with number of nodes unknown.

Sometimes, while working with the list, it somehow gets corrupted. The corrupt node is pointing to some previous node instead of next node. So a circle is created in the list.

Test for the existence of circle (i.e., check if the list is corrupt).

Replies

  • Prasad Ajinkya
    Prasad Ajinkya
    Pradeep, can we use another data structure for this? If so, then its pretty simple -

    Traverse the linked list until you do not come to the end of the List (Null pointer). Keep on storing the address in another data structure, and before storing check against all the previous entries. If a duplicate is found, then its a circle.

    But, this cant be that simple ... or is it??
  • pradeep_agrawal
    pradeep_agrawal
    kidakaka
    Traverse the linked list until you do not come to the end of the List (Null pointer).
    Consider the case when there is a circular path, in such case you will never reach the end of the list and will move along the circular path.

    kidakaka
    can we use another data structure for this?
    Yes, you can use another data structure, but try to keep the program efficient.
  • Prasad Ajinkya
    Prasad Ajinkya
    No pradeep, thats not what I said 😀

    What I said, is maintain one structure where you first look up the address before adding it to the structure. If it is already there, then it is a circular queue, if not, then only add.

    Its simple and gets the job done. Efficient, maybe not.
  • pradeep_agrawal
    pradeep_agrawal
    Sorry for wrong interpretation of the solution Kidakaka.

    The approach should work. Just my few cents:

    1. As we are using one more data structure, the solution is not optimized in terms of space complexity.

    2. Consider that the list has n nodes. For any node m, the above approach will first search the address in new data structure (say list) of size m-1. If not found, it will add the new address to the list. This make the algorithm of complexity O(n*n).

    So, all CEans, Kidakaka has already done the half task by providing you a approach. Now the next challenge for you all is to think of an optimize solution that solve above problem with less time & space complexity. You can take other approach also to solve the problem.
  • sahana
    sahana
    this is my wild guess.
    i go by kidakaka.may be we cud use a stack instead of list and do repeated push and pop.ie first push the address of the head to stack and increment the pointer of the list.check out if the address of the new node is same as that of the address in the stack.if they arent the same pop the stack and push the new address(address of the second node in the list) and increment the pointer of list.now compare again the address in stack and the address of the next node . repeat the push and pop untill the content of stack and address of the node(of list) are same.
  • pradeep_agrawal
    pradeep_agrawal
    Good try Sahana. The approach should work, but will take more space and time during execution then the approach of Kidakaka as:

    1. Using stack instead of list will consume equal space. But we need one more stack (or other data structure) to keep the address that we pop from the stack. So the space usage is double here.

    2. Consider that the list has n nodes. For any node m, the above approach may first pop up to m-1 elements from stack. If the address is not found in stack, it will push all the m-1 element back and add the new element corresponding to node m . This make the algorithm of complexity O(2*n*n) ~ O(n*n). But is taking more time then the one in case of list.

    I am sure if you work more on it, you can find a better and optimized approach.

    -Pradeep
  • sahana
    sahana
    pradeep, i am so sorry.i thought the corrupted node was pointing immediately to the previous node, so according to me i will be just using one stack with maximum one element at a time. right i got u now.

    i need one more information.can i take it for granted that these nodes are placed sequentially in the memory. i am not too sure if they are always.
    for instance i am using a variable now.i will store the address of the head of list in a variable and increment the pointer of the list.if the next node's address is greater i will overwrite the variable with the new address.repeat this process until i find adddress of a node to be lesser than the one in the variable.that means there is a cycle.

    if u want to find the exact node from which the list is corrupted construct a stack and push that particular address.decrement the pointer in the list and compare the address with the value in stack.repeat till find address and value of stack to be equal.

    i hope i am not confusing
  • pradeep_agrawal
    pradeep_agrawal
    Confusing , not at all. I got your point.

    Though its not necessary that the nodes of the list will be placed sequentially in the memory, but if we make such assumption then your solution should work.

    But finding the corrupt node process can be optimized and made simple. You find corruption by comparing address (i.e., if there is any point where address of next node is less then current node there is corruption in list). So the node at which this condition is satisfied is corrupt node).

    Goog going Sahana. Give it one more shot and you will be there.

    -Pradeep
  • sahana
    sahana
    i m sorry again.linked list must never be assumed to be stored sequentially in memory.thatz the fundamental difference between array and linked list.

    we can use 2 pointers.one pointer can jump the list say 1 node at a time while the other jumps 2 nodes at a time.initially the 2 pointers will point to head.
    keeping comparing the two pointers and iterate them respectively untill u reach null which means no cycle.if at any point the pointers point to same location ie same next location means there is a cycle.
  • pradeep_agrawal
    pradeep_agrawal
    Great work Sahana, good going. 😁

    I had few more solution, but this is the most optimized option among that. The algorithm has a time complexity of O(n) and very much optimized in terms of space complexity.

    -Pradeep
  • pradeep_agrawal
    pradeep_agrawal
    Posting a sample code as per the solution stated by Sahana.

    int IsCircle(node* head) {
        node *tmp1;
        node *tmp2;
        int result = 0;        //Specify no circular path exist
    
        tmp2 = tmp1 = head;
        while((tmp1 != NULL) && (tmp2 != NULL)) {
            //increment tmp1 by 1 and tmp2 by 2
            tmp1 = tmp1->next;
            tmp2 = tmp2->next;
            if(tmp2 != NULL) {
                tmp2 = tmp2->next;
            } else {
                break;
            }
    
            if((tmp1 == tmp2) && (tmp2 != NULL)){
                result = 1;        //specify existence of circular path
                break;
            }
        }
    
        return result;
    }
    
    -Pradeep

You are reading an archived discussion.

Related Posts

I m a b.tech student. Please suggest me. How to make system application program. I know c,c++. Suggest some mini projects also.
CEans, We get a huge number of engineering students looking for seminar topics and mini project ideas. So, let's compile all the project ideas / seminar topics we've discussed so...
Puzzle Taken from Mind and Visual Puzzles! - The parrot sequence Gaston owns a clever parrot called Paco which can describe out loud numbers read from a piece of paper...
CEans, I'm convinced that we need to reorganize our sections on CE. While we finalize on the new structure, how many of you think that we need a separate section...
HI,,,,,,,,kindly tell me hw to go to the projects ideas section ? i m from EE branch of 2nd yr.