detecting the start of a loop in a singly linked link list?

https://stackoverflow.com/questions/1536944

20-09-2019
|

Question

Is there any way of finding out the start of a loop in a link list using not more than two pointers? I do not want to visit every node and mark it seen and reporting the first node already been seen.Is there any other way to do this?

Solution

I have heard this exact question as an interview quiz question.

The most elegant solution is:

Put both pointers at the first element (call them A and B)

Then keep looping::

Advance A to the next element
Advance A to the next element again
Advance B to the next element

Every time you update a pointer, check if A and B are identical. If at some point pointers A and B are identical, then you have a loop. Problem with this approach is that you may end up moving around the loop twice, but no more than twice with pointer A

If you want to actually find the element that has two pointers pointing to it, that is more difficult. I'd go out of a limb and say its impossible to do with just two pointers unless you are willing to repeat following the linked list a large number of times.

The most efficient way of doing it with more memory, would be to put the pointers to the elements in and array, sort it, and then look for a repeat.

OTHER TIPS

Step1: Proceed in the usual way, you will use to find the loop, i.e. Have two pointers, increment one in single step and other in two steps, If they both meet in sometime, there is a loop.

Step2: Freeze one pointer where it was and increment the other pointer in one step counting the steps you make and when they both meet again, the count will give you the length of the loop (this is same as counting the number of elements in a circular link list).

Step3: Reset both pointers to the start of the link list, increment one pointer to the length of loop times and then start the second pointer. increment both pointers in one step and when they meet again, it will be the start of the loop (this is same as finding the n^th element from the end of the link list).

MATHEMATICAL PROOF + THE SOLUTION

Let 'k' be the number of steps from HEADER to BEGINLOOP.
Let 'm' be the number of steps from HEADER to MEETPOINT.
Let 'n' be the number of steps in the loop.
Also, consider two pointers 'P' and 'Q'. Q having 2x speed than P.

SIMPLE CASE: When k < N

When P would have moved from BEGINLOOP to MEETPONT, it would have traveled 'm-k' steps. In that time, Q would have traveled '2(m-k)' steps. But, since they met, and Q started 'n-k' steps behind the BEGINLOOP, so, effectively, '2(m-k) - (n-k)' should be equal to '(m-k)' So,

=> 2m - 2k - n + k = m - k
=> 2m - n = m
=> n = m

THAT MEANS, P and Q meet at the point equal to the number of steps (or multiple to be general, see the case mentioned below) in the loop. Now, at the MEETPOINT, both P and Q are 'n-(m-k)' steps behind, i.e, 'k' steps behind ,as we saw n=m. So, if we start P from HEADER again, and Q from the MEETPOINT but this time with the pace equal to P, P and Q will now be meeting at BEGINLOOP only.

GENERAL CASE: Say, k = nX + Y, Y < n (Hence, k%n = Y)

When pointer 'P' would be at BEGINLOOP (i.e. it would have traveled 'k' steps), Q would have traveled '2k' steps. So, effectively, Q is ahead of '2k-k = k' steps from P when P enters the loop. But, please note 'k' is greater than 'n', which means Q would have made multiple rounds of the loop. So, effectively, Q is 'n-(k%n)' steps behind the BEGINLOOP now.

When P would have moved from BEGINLOOP to MEETPOINT, it would have traveled 'm-k' steps. (Hence, effectively, MEETPOINT would be at '(m-k)%n' steps ahead of BEGINLOOP now.) In that time, Q would have traveled '2(m-k)' steps. But, since they met, and Q started 'n-(k%n)' steps behind the BEGINLOOP, so, effectively, new position of Q (which is '(2(m-k) - (n-k/%n))%n' from BEGINLOOP) should be equal to the new position of P (which is '(m-k)%n' from BEGIN LOOP).

So,

=> (2(m - k) - (n - k%n))%n = (m - k)%n
=> (2(m - k) - (n - k%n))%n = m%n - k%n
=> (2(m - k) - (n - Y))%n = m%n - Y   (as k%n = Y)
=> 2m%n - 2k%n - n%n + Y%n = m%n - Y
=> 2m%n - Y - 0 + Y = m%n - Y    (Y%n = Y as Y < n)
=> m%n = 0
=> 'm' should be multiple of 'n'

First we try to find out, is there any loop in list or not. If loop exists then we try to find out starting point of loop. For this we use two pointers namely slowPtr and fastPtr. In first detection (checking for loop), fastPtr moves two steps at once but slowPtr moves by one step ahead at once.

slowPtr   1   2   3   4   5   6   7
fastPtr   1   3   5   7   9   5   7

It is clear that if there is any loop in list then they will meet at point (Point 7 in above image), because fastPtr pointer is running twice faster than other one.

Now, we come to second problem of finding starting point of loop.

Suppose, they meet at Point 7 (as mentioned in above image). Then, slowPtr comes out of loop and stands at beginning of list means at Point 1 but fastPtr still at meeting point (Point 7). Now we compare both pointers value, if they same then it is starting point of loop otherwise we move one step at ahead (here fastPtr is also moving by one step each time) and compare again till we find same point.

slowPtr   1   2   3   4
fastPtr   7   8   9   4

Now one question comes in mind, how is it possible. So there is good mathematical proof.

Suppose:

m => length from starting of list to starting of loop (i.e 1-2-3-4)
l => length of loop (i.e. 4-5-6-7-8-9)
k => length between starting of loop to meeting point (i.e. 4-5-6-7)

Total distance traveled by slowPtr = m + p(l) +k
where p => number of repetition of circle covered by slowPtr

Total distance traveled by fastPtr = m + q(l) + k
where q => number of repetition of circle covered by fastPtr

Since,
fastPtr running twice faster than slowPtr

Hence,
Total distance traveled by fastPtr = 2 X Total distance traveled by slowPtr
i.e
m + q(l) + k = 2 * ( m + p(l) +k )
or, m + k = q(l) - p(l)
or, m + k = (q-p) l
or, m = (q-p) l - k

So,
If slowPtr starts from beginning of list and travels "m" length then, it will reach to Point 4 (i.e. 1-2-3-4)

and
fastPtr start from Point 7 and travels " (q-p) l - k " length then, it will reach to Point 4 (i.e. 7-8-9-4),
because "(q-p) l" is a complete circle length with " (q-p) " times.

More detail here

Proceed in the usual way you will use to find the loop. ie. Have two pointers, increment one in single step(slowPointer) and other in two steps(fastPointer), If they both meet in sometime, there is a loop.

As you might would have already realized that meeting point is k Step before the head of the loop.

where k is size of non-looped part of the list.

now move slow to head of the loop

keep Fast at collision point

each of them are k STep from the loop start (Slow from start of the list where as fast is k step before the head of the loop- Draw the pic to get the clarity)

Now move them at same speed - They must meet at loop start

slow=head
while (slow!=fast)
{
     slow=slow.next;
     fast=fast.next;
}

This is code to find start of loop in linked List :

public static void findStartOfLoop(Node n) {

    Node fast, slow;
    fast = slow = n;
    do {
        fast = fast.next.next;
        slow = slow.next;
    } while (fast != slow);       

    fast = n;
    do {
        fast = fast.next;
        slow = slow.next;
    }while (fast != slow);

    System.out.println(" Start of Loop : " + fast.v);
}

There are two way to find the loops in a link list. 1. Use two pointer one advance one step and other advance two steps if there is loop, in some point both pointer get the same value and never reach to null. But if there is no loop pointer reaches to null in one point and both pointer never get the same value. But in this approach we can get there is a loop in the link list but we can't tell where exactly starting the loop. This is not the efficient way as well.

Use a hash function in such a way that the value should be unique. Incase if we are trying to insert the duplicate it should through the exception. Then travel through each node and push the address into the hash. If the pointer reach to null and no exception from the hash means there is no cycle in the link list. If we are getting any exception from hash means there is a cycle in the list and that is the link from which the cycle is starting.

Well I tried a way by using one pointer... I tried the method in several data sets.... As the memory for each of the nodes of a linked list are allocated in an increasing order, so while traversing the linked list from the head of the linked list, if the address of a node becomes larger than the address of the node it is pointing to, we can determine there is a loop, as well as the beginning element of the loop.

The best answer I have found was here:
tianrunhe: find-loop-starting-point-in-a-circular-linked-list

'm' being distance between HEAD and START_LOOP
'L' being loop length
'd' being distance between MEETING_POINT and START_LOOP
p1 moving at V, and p2 moving at 2*V

when the 2 pointers meet: distance run is = m+ n*L -d = 2*(m+ L -d)
=> which means (not mathematicaly demonstrated here) that if p1 starts from HEAD & p2 starts from MEETING_POINT & they move at same pace, they will meet @ START_LOOP

Refer to this link for comprehensive answer.

Proceed in the usual way you will use to find the loop. ie. Have two pointers, increment one in single step and other in two steps, If they both meet in sometime, there is a loop.
Keep one of the pointers fixed get the total number of nodes in the loop say L.
Now from this point(increment second pointer to the next node in the loop) in the loop reverse the linked list and count the number of nodes traversed, say X.
Now using the second pointer(loop is broken) from the same point in the loop travrse the linked list and count the number of nodes remaining say Y
The loop begins after the ((X+Y)-L)\2 nodes. Or it starts at the (((X+Y)-L)\2+1)th node.

Proceed in the usual way you will use to find the loop. ie. Have two pointers, increment one in single step and other in two steps, If they both meet in sometime, there is a loop.
Keep one of the pointers fixed get the total number of nodes in the loop say L.
Now from this point(increment second pointer to the next node in the loop) in the loop reverse the linked list and count the number of nodes traversed, say X.
Now using the second pointer(loop is broken) from the same point in the loop travrse the linked list and count the number of nodes remaining say Y
The loop begins after the ((X+Y)-L)\2 nodes. Or it starts at the (((X+Y)-L)\2+1)th node.

void loopstartpoint(Node head){
    Node slow = head.next;;
    Node fast = head.next.next;

    while(fast!=null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;

        if(slow==fast){
            System.out.println("Detected loop ");
            break;
        }
    }

    slow=head;
    while(slow!=fast){
        slow= slow.next;
        fast = fast.next;
    }
    System.out.println("Starting position of loop is "+slow.data);
}

detect loop
copy each element's address into set. If duplicate is found that's the start of the loop

Licensed under: CC-BY-SA with attribution

Not affiliated with StackOverflow