Circular linked list logic

Question

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
          ListNode slow = head;
          ListNode fast = head.next;

          while((slow != null) && (fast != null) && (slow.next != null) && (fast.next != null)){
            if(slow == fast){
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;

          }

          return false;
    }
}

For detecting a circular linked list, we use the 2 pointer technique, slow and fast.

My question is, how do I know the pointers must intersect at some point if the list is a circular list?

Answer 1

Look at a watch. That is a circular list of numbers 1 to 12 then circles back to 1.

The big hand is moving fast, the small hand is moving slow, both moving in the same direction, and starting at the same point (top = 12).

Because the list (edge) is circular, the big hand will eventually catch back up to the small hand. How quickly depends on the speed difference, but it will catch up. If it catches up, the list must be circular.

If it doesn't catch up, but gets to end of list, the list is not circular.

Even if the list doesn't circle back to the beginning, e.g. if 12 circled back to 9, the fast hand would just keep circling, until the small hand enters the circle, and then the fast hand will eventually catch up to the small hand.

Ok, for that last part, the image of a watch wasn't good, but I hope you got the point.