We all knw hw to find a loop in a singly linked list (Using hare and
tortoise method)..what if the linked list is a doubly linked list?can
we do it smthn better than hare n tortoise method using the advantage
of the doubly linked list?
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-7483122727*
*
if we take 2 pointers initialized with the start node with one moving in
forward direction and other in backward direction and execute until both
point to same node .it cud be workin faster i suppose...
On Thu, Aug 18, 2011 at 1:21 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote:
We all knw hw
But it is not circular doubly linked list.,..so u could not traverse in
backward dirction from HEAD node..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
WHERE will the back pointer of intersecting node will point?
On Wed, Aug 17, 2011 at 3:47 PM, Brijesh Upadhyay
brijeshupadhyay...@gmail.com wrote:
But it is not circular doubly linked list.,..so u could not traverse in
backward dirction from HEAD node..
--
You received this message because
At the node from where the loop just started.. anyway we could not use that
logic , coz it isnt circular linked list!
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
ys...i guess i misinterpreted..the question..
ma fault...
On Thu, Aug 18, 2011 at 4:27 AM, Brijesh Upadhyay
brijeshupadhyay...@gmail.com wrote:
At the node from where the loop just started.. anyway we could not use that
logic , coz it isnt circular linked list!
--
You received this message
I have come up with this:
- Use only one pointer, NODE *cur
- initialize cur to headref
- The main loop:
while (cur)
{
if(cur-next-prev != cur)
break;
cur=cur-next;
}
return cur;
^^ I think the code is self explanatory. It just uses the fact that at loop,
the prev of next to current
A slight change in above code:
make it
while(cur cur-next)
^^ other wise the code will crash at last element in a prefect list, with no
loop.
On 18 August 2011 07:36, Dipankar Patro dip10c...@gmail.com wrote:
I have come up with this:
- Use only one pointer, NODE *cur
- initialize cur to