Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:

Can you solve it without using extra space?

/*
Definition for singly-linked list.

public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}
*/

public class Solution {
  public ListNode detectCycle(ListNode head) {
        
  }
}

This problem is selected from Leetcode.

Solution

Use a fast pointer and a slow pointer to traverse the list from the head. Each time the fast pointer moves 2 steps while slow pointer moves 1 steps. If the fast pointer meets the slow pointer somewhere in the list, that means the list has a cycle. But how to return the node where the cycle begins?

The key of this is finding out the relationship between the meeting nodes of the two pointers and the start node of the cycle.

Assume the distance between the start of the cycle and the head of the list is d_cycle, the length of the cycle is l_cycle, and the meeting point of the two pointers is d_meet away from the start of the cycle.

Then, the slow pointer moves (d_cycle+m*l_cycle+d_meet) steps.

The fast pointer moves (d_cycle + n * l_cycle + d_meet) steps.

As they meet each other, so 2*(d_cycle+m*l_cycle+d_meet) equals (d_cycle + n * l_cycle + d_meet).

So we have, d_cycle+d_meet = (n-2*m)l_cycle.

Here, for any n and m, if they satisfy the above equation, the two pointers will meet each other. So we simply take n=1 and m=0, then we have

d_cycle = l_cycle – d_meet

Now if we setup two pointers moving along the list. One pointer, A, starts from the head of the list and the other one, B, starts from the meeting point of the previous slow and fast pointer. After A moves d_cycle steps, B has moved l_cycle – d_meet steps. Both of them will at the start of the cycle.

public class Solution {
  public ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    
    while(fast!=null) {
      fast = fast.next;
      if(fast==null) break;
      fast = fast.next;
      if(fast==null) break;
      
      slow = slow.next;
      
      if(fast==slow) {
        int nodeA = head;
        int nodeB = slow;
        while(nodeA!=nodeB) {
            nodeA = nodeA.next;
            nodeB = nodeB.next;
        }
        return nodeB;
      }
    }
    return null;
  }
}

RelatedPost