pradeep_agrawal

Branch Unspecified

02 Mar 2008

**Data Structure/Algorithm Challenger II**

We have a doubly-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).

Note: The list is doubly and not singly like Data Structure/Algorithm Challenger I, so a solution other then one specified in Data Structure/Algorithm Challenger I is expected.

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).

Note: The list is doubly and not singly like Data Structure/Algorithm Challenger I, so a solution other then one specified in Data Structure/Algorithm Challenger I is expected.

sahana

Branch Unspecified

16 Mar 2008

some hint please. isnt the one by single linked list considered to be the most optimal?i jus hav a vague idea.may be we can have two pointers that go in opposite directions and if they dont meet means there is a cycle.i dont know where my second pointer ie which is to travel back wards has to point initially because i am not given the number of nodes.

pradeep_agrawal

Branch Unspecified

17 Mar 2008

The solution given for singly linked list may be optimal for it, but a more optimized solution may exist for doubly linked list.sahanaisnt the one by single linked list considered to be the most optimal?

We can't have second pointer pointing to the last node of list because we have only head and if the list is corrupt we never reach the last node. Due to same reason we canit count the number of nodes in the list.sahanamay be we can have two pointers that go in opposite directions and if they dont meet means there is a cycle.i dont know where my second pointer ie which is to travel back wards has to point initially because i am not given the number of nodes.

The basic property of doubly linked list is that every node has two pointers, one pointing to next node and other pointing to previous node in the list. Having an extra pointer in each node surely increase the space complexity, but that will help in giving more optimized solution to the problem in terms of space complexity.sahanasome hint please.

-Pradeep

pradeep_agrawal

Branch Unspecified

10 Nov 2008

No solution from such a long time 😔

Here is a sample code for the given problem statement. Solution is based on fact that in a doubly linked list, previous of next of a node is the same node. The solution has complexity of O(n).

Here is a sample code for the given problem statement. Solution is based on fact that in a doubly linked list, previous of next of a node is the same node. The solution has complexity of O(n).

n[FONT=Verdana]ode *tmp1 = head;[/FONT] [FONT=Verdana]int result = 0; //Specify no circular path exist[/FONT] [FONT=Verdana]while(tmp1 != NULL) {[/FONT] [FONT=Verdana] if(tmp1->next != null) {[/FONT] [FONT=Verdana] if(tmp1->next->prev != tmp1) {[/FONT] [FONT=Verdana] result = 1; //specify existence of circular path[/FONT] [FONT=Verdana] break;[/FONT] [FONT=Verdana] }[/FONT] [FONT=Verdana] tmp1 = tmp1->next;[/FONT] [FONT=Verdana] } else {[/FONT] [FONT=Verdana] break;[/FONT] [FONT=Verdana] }[/FONT] [FONT=Verdana]}[/FONT] [FONT=Verdana]return result;[/FONT]-Pradeep

sumitjami

Branch Unspecified

17 Nov 2008

hey the above code checks only between the two nodes but instead if we can modify the data node then include a flag.........

1>> initialize all flags to false......

2>> Goto each node serially and in each node check if its flag is already true is so then it means that the node has been already visited once and thus there exits a loopbut if the flag is false set it to true and iterate further........

<thus any size loop can be detected>

1>> initialize all flags to false......

2>> Goto each node serially and in each node check if its flag is already true is so then it means that the node has been already visited once and thus there exits a loopbut if the flag is false set it to true and iterate further........

<thus any size loop can be detected>

pradeep_agrawal

Branch Unspecified

17 Nov 2008

Yes this can be a solution but:sumitjamihey the above code checks only between the two nodes but instead if we can modify the data node then include a flag

1. It will need modification of your base data structure, which you may not always want to do.

2. Keeping an extra flag in each node will consume more memory.

-Pradeep

Only logged in users can reply.