CODEWITHSUNDEEP
cpointersdoubly-linked-list
Fouad Wahabi
Fouad Wahabi

Reputation: 804

Determing if the head of a circular doubly-linked list is part of a "jump" cycle

There's a doubly linked list which is also circled (i.e., the last node's next pointer points to the head of the list and the head's prev pointer points to the last node).

The data in each node is an integer.

A jump in a circular list is defined as follows for a node p :

I need to write a method that receives a pointer to the head of the list as a parameter and returns true if there's a jump path that starts and ends at the head node.

An example list:

 node | data | next | prev
------|------|------|------
   0  |   2  |   1  |   5
   1  |  14  |   2  |   0
   2  |  -5  |   3  |   1
   3  |   1  |   4  |   2
   4  |  -4  |   5  |   3
   5  |   1  |   0  |   4

For this list, the method should return true. Starting at the head (node 0), we move forward twice to node 2, then back 5 times to node 3, forward once to node 4, and finally back 4 times, returning to node 0:

 node  | jumps | next node
-------|-------|-----------
   0   |   2   |     2
   2   |  -5   |     3
   3   |   1   |     4
   4   |  -4   |     0

My main problem is when I should return false.

This is not homework (I'm working on different exercises in order to prepare my self for an exam)

Upvotes: 2

Views: 185

Answers (2)

Soumyajit Chatterjee
Soumyajit Chatterjee

Reputation: 63

First decide when the method will stop i.e. what is the halting condition as given your question above again the method will start moving and will return to 2 and this process will continue ever. The only halting condition specified above is the occurrence of zero in the zero otherwise this program will never halt.

If coming to the head node can also result in halting of the program then the code can be completed in this way:

findHead(head,originalHead,calledCount){
    if(originalHead==null)
    {
        return false;
    }
    else if (head==originalHead && calledCount>1) 
    /*If while roaming gets to the head then returns true but except the first time where the head will always be equal to original head */
    {                   
        return true;
    }
    else {
        p=head;
        if(p.data>0)
        {
            steps=p.data;
            while(steps>0)
            {
                p=p->next;
                steps--;
            }
            findHead(p,originalHead,calledCount);
        }
        else if(p.data<0)
        {
            steps=p.data;
            while(steps<0)
            {
                p=p->prev;
                steps++;
            }
            findHead(p,originalHead,calledCount);
        }
        else    // If obtained 0 in the list
        {
            if (p==originalHead)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
    calledCount++;
}

Upvotes: -1

CMoi
CMoi

Reputation: 846

There are plenty of ways to do it.

For example you can return false if you didn't get back to the head after n jumps (n being the length of the list) as it means you are looping in another part of the list.

You can also mark the visited nodes and return false if you visit twice any node (apart from the head).

You also have to return false directly if you reach a 0 which is not the head of the list.

Upvotes: 4

Related Questions