linked lists question

[Rajesh Inakota]

We all know how to find loop in single linked list.

Now the question is, how do you find the starting node/ending node of the loop and make ending node to null.

--
Regards,
Rajesh.I

[Thumbeti Sivaramaiah]

Does the list has any property?
Like, all the elements in the list following any rule.. etc
~Siva

[Rajesh Inakota]

1->4->2->3->5->2(loop).

simple linked list, no rule.

--
Regards,
Rajesh.I

[Rajesh Inakota]

at the end, you should able to come up with

1->4->2->3->5->null.

--
Regards,
Rajesh.I

[Thumbeti Sivaramaiah]

Thanks Rajesh. One more clarification in the same lines.

Complete loops are also treated as valid inputs?
EX: 1->4->2->3->5->1(loop)

[Rajesh Inakota]

if its an complete loop, there won't be clue for merge point, it becomes proper circular linked list.

without head pointer it becomes difficult.

Complete loops can be eliminated. 

--
Regards,
Rajesh.I

[Shyam Prakash Velupula]

The easiest of the solutions (probably something your are not looking for) is to to assume the given node as the starting point. Save all the pointers visited in another list. Any address that is repeated (check against saved addresses) would emerge from the last node in the list (make it point to NULL).

-Shyam

--
You are limited only by your imagination

[Shyam Prakash Velupula]

first try, this won't work for a complete cycle as Siva pointed.

Make a copy of the original list (Lo) and name it Ld.

Lo: 1->4->2->3->5->2 (loop)

Ld: 1->4->2->3->5->2 (loop)

Traverse Ld and reverse pointers while doing so

1<-4<-2<-3<-5 (till this point, we haven't traversed looped 2 from 5)

1->4->2<-3<-5<-2, after 5->2 is explored, 4, 1 gets traversed again and this re-reverses the links to it's original. Due to this the mini loop get reversed in direction.

Use Lo & Ld and traverse 1 node at a time till  we find a divergent point (2->3 in Lo and 2->5 in Ld).

Details from Ld can be used to find the merge point (2) and list end point (5). 

- Shyam

[Rajesh Inakota]

1->4->2->3->5->2 (loop)

what if repeated node is 3 while detecting loop.

1->4->2->3->null

5->2->3->null

On Tue, Jul 12, 2011 at 2:32 PM, Shyam Prakash Velupula <velu...@gmail.com> wrote:

--
Regards,
Rajesh.I

[Shyam Prakash Velupula]

Compare pointers not the values. Values are for illustration purpose only.

[Rajesh Inakota]

Yes I am considering 3 as node address. Loop detection can't say end of the list.

Probably you can give illustration with example.

--
Regards,
Rajesh.I

[Rajesh Inakota]

Sorry, I am thinking of two pointers .. yes it is correct ..

--
Regards,
Rajesh.I

[Rajesh Inakota]

There are multiple variants of solutions,

From Bhargav:

  using loop detection, 1 step 2 step algorithm find the length of the cycle.

  place two pointers at head, and make one pointer move length calculated in first step.

  now keep moving both pointers until one pointer meets other, this is merging pointer.

There is very good solution on this check below link,

http://umairsaeed.com/2011/06/23/finding-the-start-of-a-loop-in-a-circular-linked-list/

Suresh:

 If you know other solutions apart from this, you can share with us.

--
Regards,
Rajesh.I

[bhargava]

Consider the same

1->4->2->3->5->3

upto the time we reach 5
1<-4<-2<-3<-5->3
after passing through 5->3 and coming back to 1, you would still end up with the same list
1->4->2->3->5->3

if we have just one element in the list, would you be able to distinguish it ? 3->5->3 ?

[Shyam Prakash]

Is this for me Bhargav?

Looks like groups is not doing a good job of indenting replies?
Please use names while commenting to make it clear, who needs to
respond.

-Shyam

[Rajesh Inakota]

Google wave will serve better i guess :)

--
Regards,
Rajesh.I

[bhargava]

Shyam,

Would you be able to detect a direct node loop

1->2->3->4->5->5 ?

[bhargava]

While replying from groups website, it is not including the context, unless we explicitly click 'Quote Original'

On Tuesday, 12 July 2011 15:42:53 UTC+5:30, Shyam Velupula wrote:

Is this for me Bhargav?

Looks like groups is not doing a good job of indenting replies?
Please use names while commenting to make it clear, who needs to
respond.

-Shyam

[Rajesh Inakota]

underneath every reply there will be  -Show quoted text -.  we can click on that to see the context.

--
Regards,
Rajesh.I

[bhargava]

Rajesh,

How do you reply to groups mail, using groups website or gmail ?

If using gmail, it will automatically add the context, groups does not seem to using this as default
This reply should not have context

[Rajesh Inakota]

Yes using gmail.

--
Regards,
Rajesh.I

[Shyam Prakash Velupula]

Looks like I will have to revisit my answer.

-Shyam

[SURI]

First of all, I am not sure about replying using gmail but reply using g-groups with proper reply button will surely maintain the proper hierarchy. 

Let us try to make a habit when replying to a specific post : 

       1. Using the proper reply button  

       2. Acknowledge the name of the person that you are referring.

       3. If you are commenting about the specific line in the previous comment then better reuse that line prefixed with ">>"

       and Lets not keep many open threads running parallel ..

As far as I recall there are multiple solutions for this ..

1. The more elegant one is the one specified in the link ..

           a. It is based on the principle that in any complete circular list, starting two pointer at a specific point, say at node X, and at each step incrementing one pointer by one and other by two then they both meet at the node X. 

                       If we closely observe the behavior then we know why the above one is true.

            

2. The solution Shyam was proposing, With the extra O(n) memory and with reversing the pointers in another copy.

           a. Make a duplicate copy (and store the addresses of the original list used for comparison purpose), Say List-2.

           b. Find the loop using the regular (+1, +2) method and assume both pointer meet at a node say Y.

           b. Reverse the pointers in the second list.

           c. Calculate the distance from head to Y using original list, Say List-1.

           d. Calculate the distance from head to Y using List-2.

           e. Keep two pointers (one P1 on List-1 and another one P2 on List-2) starting at position Y and move towards to root using two different directions.. Decrement the longer list pointer by difference.

           f. Compare P2 value with the address of P1 by decrementing position by position.

3. Even worse than the earlier two..

           a. Find the loop. Assume both pointers meet at Y. Start pointer P1 at Y.

           b. FInd the distance between root and P1. 

           c. Increment the P1 and find the distance, if the current distance < previous distance then call this as loop node.

           d. To decrease the number of distance calculations we can use one sided binary search logic to increment the pointer P1.

  

-- SURI