# A C# 6-Line Solution

• ``````public ListNode DetectCycle(ListNode head) {
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;
}``````

• 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
//

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
return NULL;

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 *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;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.