public ListNode DetectCycle(ListNode head) {
if(head == null  head.next == null) return null;
ListNode p1 = head.next;
for(ListNode p2 = head.next.next; p1 != p2  p2 == null; p1 = p1.next, p2 = p2.next.next)
if(p2 == null  p2.next == null) return null;
for(ListNode p2 = head; ; p1 = p1.next, p2 = p2.next) if(p1 == p2) return p1;
return null;
}
A C# 6Line Solution


CPP code with explanation based on lestrois's solution.
// slow: 1 nodes/sec // fast: 2 nodes/sec // // The cycle has M nodes. At time t0, the slow is the first node in the cycle, // the fast is the n node. t0 % M == n // After t seconds, slow and fast meet. t % M == (2t + n) % M // t + k*M == 2t + n // t = k * M  n // k == 1 is the frist meet. At this time, t = M  n; // So the first time slow and fast meet, slow has not scaned the cycle one time. // // t0 = x * M + n // /** * Definition for singlylinked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { if (NULL == head  NULL == head>next) return NULL; // Reverse head ListNode *slow = head; ListNode *fast = head>next; while (slow != fast) { if (NULL == slow>next) return NULL; if (NULL == fast>next  NULL == fast>next>next) return NULL; slow = slow>next; fast = fast>next>next; } ListNode *node = head; ListNode *cycle_node = slow>next; // It takes t0 seconds from head to the first node of the cycle // t0 = x * M + n // It needs n seconds from meet to the first node of the cycle // So node and cycle_node will meet at the first node of the cycle while (node != cycle_node) { node = node>next; cycle_node = cycle_node>next; } return node; } };