Detect a cycle in a linked list and return the node where the cycle?

begins

public class ListNode {

public int val;

public ListNode next;

public ListNode(int x) { val = x; next = null; }

ListNode DetectCycle(ListNode head) {

if (head == null) return null;

ListNode slow = head, fast = head;

Follow on:

// Detect cycle using Floyd's Tortoise and Hare

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

slow = slow.next;

fast = fast.next.next;

if (slow == fast) { // cycle detected

ListNode ptr = head;

while (ptr != slow) {

ptr = ptr.next;

slow = slow.next;

return ptr; // start node of cycle

return null; // no cycle

Explanation:

First detect cycle meeting point with two pointers. Then find start node by moving one

pointer from head and one from meeting point until they meet.