7

I'm trying to find the point of a singly link list where a loop begins. what I thought of was taking 2 pointers *slow, *fast one moving with twice the speed of other. If the list has a loop then at some point

    5-6-7-8
    |     |
1-2-3-4-7-7

slow=fast

Can there be another elegant solution so that the list is traversed only once?

Brian Tompsett - 汤莱恩
  • 5,753
  • 72
  • 57
  • 129
ishan soni
  • 92
  • 7
  • Traverse the list, count the nodes, midpoint = number of nodes/2 rounded to closest int – peacemaker Aug 10 '12 at 21:17
  • 1
    @peacemaker You’d still have to traverse the list until the midpoint then. – Konrad Rudolph Aug 10 '12 at 21:18
  • @KonradRudolph Right, 1 traversal of the list will get you the midpoint, like OP asked – peacemaker Aug 10 '12 at 21:19
  • 1
    @peacemaker: That'd be one and a half traversals. – Will Vousden Aug 10 '12 at 21:19
  • 2
    What do midpoints have to do with loops in the list? Do you want to find the start of the loop? – Todd Li Aug 10 '12 at 21:20
  • @WillVousden No, you'd only traverse the list one time, counting the nodes as you go. After the traversal you can find the midpoint simply by dividing number of nodes by 2. – peacemaker Aug 10 '12 at 21:21
  • 2
    @peacemaker: Sure, you've found the index of the midpoint, but then you have to access it. In the case of a linked list, that means traversing the first half of the list again. Linked lists have O(n) access time. – Will Vousden Aug 10 '12 at 21:22
  • @WillVousden Ahh yes, good point! – peacemaker Aug 10 '12 at 21:24
  • sorry guys i got you off record...i edited the ques...i made a mistake..but about midpoint again take 2 pointers.slow and fast,with fast moving at twice the speed,when fast==NULL,the slow pointer will be at the mid position,if no of elements are odd,but with even elements,the element left to *slow will also be the mid element.that make a single traversal....now answer about the loop one? – ishan soni Aug 10 '12 at 21:30
  • @YuxiuLi sorry about that miss typed ques....ya i want to find the start point of the loop in a single traversal. – ishan soni Aug 10 '12 at 21:35
  • Duplicate of http://stackoverflow.com/questions/2663115/interview-question-how-to-detect-a-loop-in-a-linked-list – Jim Balter Aug 10 '12 at 23:12

3 Answers3

4

Your idea of using two walkers, one at twice the speed of the other would work, however the more fundamental question this raises is are you picking an appropriate data structure? You should ask yourself if you really need to find the midpoint, and if so, what other structures might be better suited to achieve this in O(1) (constant) time? An array would certainly provide you with much better performance for the midpoint of a collection, but has other operations which are slower. Without knowing the rest of the context I can't make any other suggestion, but I would suggest reviewing your requirements.

Andrew Ring
  • 3,185
  • 1
  • 23
  • 28
2

I'm assuming that this singly linked list is ending with NULL. In this case, slow pointer and fast pointer will work. Because fast pointer is double at speed of slow one, if fast pointer reaches end of list slow pointer should be at middle of it.

Bharat Kul Ratan
  • 985
  • 2
  • 12
  • 24
2

I am assuming this was some kind of interview question.

If your list has a loop, then to do it in a single traversal, you will need to mark the nodes as visited as your fast walker goes through the list. When the fast walker encounters NULL or an already visited node, the iteration can end, and your slow walker is at the midpoint.

There are many ways to mark the node as visited, but an external map or set could be used. If you mark the node directly in the node itself, this would necessitate another traversal to clean up the mark.

Edit: So this is not about finding the midpoint, but about loop detection without revisiting already visited nodes. Marking works for that as well. Just traverse the list and mark the nodes. If you hit NULL, no loop. If you hit a visited node, there is a loop. If the mark includes a counter as well, you even know where the loop starts.

jxh
  • 69,070
  • 8
  • 110
  • 193
  • and another thing about that mid point ques,if you are having even nodes,there would be two mid points,how to find both of them? – ishan soni Aug 10 '12 at 21:45
  • You move the slow walker after the fast walker has moved. The fast walker determines whether or not the iteration continues. So, for an even number, the midpoints are the current position of the slow walker and the next one. For odd, the current position of the walker is the midpoint. – jxh Aug 10 '12 at 21:49
  • suppose we dont know the length of the list ,and we have to do it in a single traversal,then as u said we move the slow pointer after the fast pointer,and till fast=Null we also count the nodes,if nodes=even then slow and slow->next would give the answer if odd then slow->next is the answer...is that right???? – ishan soni Aug 10 '12 at 21:58
  • @ishansoni: Yes, you count the nodes. For odd, the answer is just slow, not slow->next. – jxh Aug 10 '12 at 22:01