142

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode DetectCycle(ListNode head) {
        var temp = head;
        var set = new HashSet<ListNode>();
 
        while (temp != null) {
            if (set.Contains(temp))
                return temp;
 
            set.Add(temp);
            temp = temp.next;
        }
 
        return null;
    }
}

Using a hashset, this works.

---

But we can do it with constant space.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode DetectCycle(ListNode head) {
        var slow = head;
        var fast = head;
 
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
 
            if (slow == fast) {              // phase 1: they met inside the cycle
                var p = head;                // phase 2: restart one pointer at head
                while (p != slow) {
                    p = p.next;
                    slow = slow.next;
                }
                return p;                    // cycle start
            }
        }
 
        return null;                         // no cycle
    }
}

Idea: run the same slow/fast pointers as 141. When they meet, you know there’s a cycle. Then put one pointer back at head, and move both pointers one step at a time. They meet again exactly at the cycle’s start.

Why it works:

• Let F = distance from head to the cycle start, a = distance from the cycle start to the meeting point, and C = cycle length.
• Slow has walked F + a. Fast has walked 2(F + a), which is also F + a plus some whole number of extra laps: F + a + k*C.
• So F + a = k*C, which means F = k*C - a.
• Walking F steps from the meeting point goes forward k*C - a, which brings you to the cycle start (you’re a past the start, so going C - a more completes the lap, plus any extra full laps).
• A pointer from head also takes F steps to reach the cycle start, so both arrive there together.

It’s a known result (Floyd’s algorithm).