Data Structure/Algorithm Challenger I

[pradeep_agrawal]

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

[kidakaka]

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]

Originally Posted by 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.

Originally Posted by kidakaka

can we use another data structure for this?

Yes, you can use another data structure, but try to keep the program efficient.

[kidakaka]

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]

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]

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]

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]

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]

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]

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.