An Easier One [Problem of the week]

if you think last week’s problem from Alaa wasn’t that easy. 😀
and mine in the week before that was a little strange. 😀

so this week the problem will be a bit easier.. in spite of the fact that i couldn’t solve it right a way in an interview .. but i grew smart enough to solve it yesterday.. “i think its the salad 😎 ”
“some salad picture goes here .. but i couldn’t find any nice one”

How to detect a Cycle in a Linked List ??

image

Rules:

  1. you are not Allowed to use any other data structures in you solution, no stacks no arrays no other lists .. nothing!
  2. the list is single linked .. a very normal list i mean
    and you are not allowed to change this class or add a Visited Boolean or any similar trick .. u can assume that the list Nodes are like…
    Class Node
    {
        int val;        //assuming this is an integer List
        Node next;    //this is a pointer for those who doesnt know C#
    }
  3. you can use any constant number of temporary variables or pointers .. as long as the number is constant (i want an in place algorithm) — i suggest 4 or 5 extra pointers
  4. you are not required to keep the list intact .. you may play with it or destroy it as you please 😀
  5. i don’t strictly require the source code .. just the idea .. but i may request it later if you insist that your answer is right 😀
  6. THOSE WHO ARE AFRAID OF BEING WRONG .. please go away .. if you are afraid of getting it wrong yo will never try .. then you will never get it right
  7. note 6 does not mean throwing me some idea and i have to think about it :@ .. you have to be 80% sure of your solution and think how may it go wrong and all the cases ..
  8. Read the comments -if there is any- before you post your solution .. it might remind you of some thing you forgot in your solution 😉

if you would like the next problem to be about some certain topic, then please tell me in the comments .. and it would be great if you said that in the very comment where you place your solution 😀

———–
now to the winners:
 
 
thanks every one
and still no one requested a topic for the next week’s problems! .. seems like it will be very hard one (6) !
Advertisements

17 thoughts on “An Easier One [Problem of the week]

  1. //Assumption: firstNode is a Node reference variable ( C++: Node pointer ) holding the reference of the first Node on the given linked list.

    bool circleDetected = false;
    Node dummyNode = new Node();
    Node currentNode = firstNode;

    while (currentNode.Next != null && currentNode.Next != dummyNode)
    {
    Node nextNode = currentNode.Next;
    currentNode.Next = dummyNode;
    currentNode = nextNode;

    }

    if (currentNode.Next == dummyNode)
    circleDetected = true;

    Same concept can be applied by manipulating the value member variable, but didn’t want my code to be dependent on it or to make it overwrite any data..

    Another solution, a highly retarded one, by retarded I mean extremely slow, but it’s still a solution and this is the only reason I’m posting it.
    Traversing a linked list (a circular singly linked list or a a normal singly linked list containing a circle) without knowing its size is an infinite operation because it’s not known when the list terminates, we don’t have a ending node pointing to null or other special marks! Meaning, specific nodes(ones forming the circle) will be accessed over and over! This is the key to following retarded solution, I won’t even waste more time explaining it..
    ===================
    bool circleDetected = false;
    Node currentNode = firstNode;
    int counter = 0;

    while (currentNode.Next != null && !circleDetected)
    {
    Node innerCurrentNode = firstNode;

    for (int i = 0; i < counter; i++)
    {
    if (innerCurrentNode == currentNode)
    {
    circleDetected = true;
    break;
    }
    innerCurrentNode = innerCurrentNode.Next;
    }

    counter++;
    currentNode = currentNode.Next;
    }
    ===================
    If there is a cycle, it will be detected when the the connecting node is accessed for the SECOND time. If someone doesn’t get the idea behind this solution, then never mind :]

  2. In a single loop, use two pointers to traverse the linked list. One pointer is moving one node per iteration while the other pointer is moving two nodes per iteration. In each move of the two pointers, check if the two pointers are equal or not (equal means point to the same memory location). If the linked list is not cyclic, the two pointers should never collide except at the beginning of the loop. If, during the loop, the two pointers collide, then the linked list is cyclic.

  3. looooooooool .. tab ma kont te2ool 😀
    la2 lessa coming more ones isA ..
    and btw .. your second solution is also right .. i haven’t traced the code yet .. but the idea is right

  4. I remember I read a solution to this problem smwhere before .. it some algorithm for some guy keda .. 7ageeb esmo wa2ollak 😀

    The idea is based on using two pointers at different speeds, one moves twice the other. If a loop exists, they should overlap at some point. To implement this, three pointers are used actually, one as the slow pointer, and the other two act as the fast one (first = second.Next .. second = first.Next) ..
    If at any point (slow == first || slow == second) then there’s a loop .. this procedure stops when the slow pointers reaches the last node in your linked list.

  5. Using two pointers for the linked list starting from the head, one pointer is moving one node and the other pointer is moving two nodes at a time and check if the two pointers are equal, if so there is a cycle

  6. Actually this problem is well known I think 🙂 .. I was asked about it before in an interview too..
    I think the best solution is to do it linearly using two pointers, one of them moving as twice as fast as the other.. if the linked list is cyclic, they will eventually meet somewhere in the list (ptr1 == ptr2) .. if not, the faster pointer will reach the end of the list (null)..

  7. seems i will reveal the answer very soon 😀
    another two got it right .. (Y) .. that makes 5 😀
    Mohamed Abdelghani and Roaa
    thanks guys

  8. ok ……. you said i can play with the list as i want

    so i think i can first make the program make a new node with a new pointer and save the pointer of this node in a variable …..then loop throw the list …..and each node i pass throw i remove the pointer it points to and make it point to my node that i made first (of course this step will need some variables ) and while i am looping throw the list i check if the node points to the node that i made first or not if it points to it then there is a cycle

  9. the version i like ..
    traverse the list .. reversing it as you go (swapping pointers).. then if it has a cycle.. eventually you will be back to the Head

  10. Pingback: Link-the-Tree [Problem of the Week] « AlaaShaker’s Weblog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s