Java two pointers solution


  • 9
    M
    public ListNode detectCycle(ListNode head) {
        ListNode p1 = head;
    	ListNode p2 = head;
    	while(p2 != null && p2.next != null){
    		p1 = p1.next;
    		p2 = p2.next.next;
    		if (p1 == p2) break;
    	}
    	if (p2 == null || p2.next == null){
    		return null;
    	}
    	p1 = head;
    	while(p1 != p2){
    		p1 = p1.next;
    		p2 = p2.next;
    	}
    	return p2;
    }
    

    the trick is that two pointers meet x positions before the loop start in the cycle body, where x is
    the distance from head to cycle start.


  • 0
    L

    It works! Great solution!
    But how to explain the distance is exactly x?


  • 0
    M

    loop start is at x. when fast pointer moved 2x (at position x in the loop),
    slow pointer moved x (at position 0 in the loop). let y be the length of the loop, solve (x + 2t) - (0 + 1t) = y we get t = y - x. that is, 0 + y - x = x + 2(y - x) mod y Hope that helps.


  • 0
    O

    It's kind of hard to figure out the distance is actually the same. But once some one told me it is the same, the verification is pretty easy...


  • 0
    T

    it's easy to see how it works, once you realize that the "delta/distance" between the fast and slow pointers are INCREASING by 1 per step before they meet, and once they both enter the loop, the fast pointer is catching up to the slow one by a pace of 1 per step.

    https://docs.google.com/presentation/d/1b7Hwb71H5m6x4ePw_73hpF1JagC6oHJLkJXZf14wSPE/edit?usp=sharing

    for simplicity of illustration, say at the time the slow pointer arrives at the bifurcation point, fast pointer has not wrapped around in the loop, and is X steps ahead of the slow pointer, as we said, the DELTA between them is growing at 1 per step, same speed as the slow pointer. so the DELTA must be the same distance as the distance traveled by the slow pointer. so the HEAD must be X steps back.

    now from the time when slow pointer reaches bifurcation, to when they meet up, the distance caught up by fast pointer, must be the same as the distance traveled by the slow pointer. let's refer to this as D in the figure. the distance traveled by p2 after meeting is X -D + D , same distance as traveled by p1 from head to bifurcation point


  • 0

  • 4
    Y

  • 0
    L

    What's wrong with java ? Same idea using c++ got AC, but implementing it in java got a TLE,
    even copying your code didn't work. Did they add a new test case?


  • 1
    B

    I'll try to explain Meowgadeth's code a little bit, for his explaination seems not precise enough:

    Let the cycle length be L, cycle starts at node[s], noted as c[0].

    When p1 reached node[s] = c[0], p2 reached node[2s] = c[s]*.

    Now p1 is L-s steps ahead of p2 in the cycle, so after L-s moves p2 will meet p1 at node[L] = c[L-s], from where p2 will reach node[s] = c[L] = c[0] after s steps.

    Note: when L < s, L-s should be (L - s) % L.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.