public ListNode detectCycle(ListNode head) {
if (head == null  head.next == null) {
return null; // no circle
}
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) { // circle detected
while (head != fast) {
fast = fast.next;
head = head.next;
}
return head;
}
}
return null; // no circle
}
Java twopointer solution.


@yhvivian You can find patterns. Most of the times, cycle detection problems can be solved using twopointers.

A bit explaination.
Provide the X is the length from head to the start point of circle and Y is the length of the circle. We know slow moves t, while fast moves 2t. They meet at K where is the length from the start point of the circle.
Then we have :t = X + nY + K 2t = X + mY + K
, then we get
X+K = (m2n)Y
which means when they meet at K, the length from K to start point of the circle is just the X. At this moment, we use a head pointer to move by the same step (=1), and they must meet at the start point of the circle which we want.

@jasonloveoj said in Java twopointer solution.:
A bit explaination.
Provide the X is the length from head to the start point of circle and Y is the length of the circle. We know slow moves t, while fast moves 2t. They meet at K where is the length from the start point of the circle.
Then we have :t = X + nY + K 2t = X + mY + K
, then we get
X+K = (m2n)Y
which means when they meet at K, the length from K to start point of the circle is just the X. At this moment, we use a head pointer to move by the same step (=1), and they must meet at the start point of the circle which we want.
One further step to make it more clear:
X = (Y  K) + (m  2n  1)Y
which means by finishing the rest length of the circle and some number of circle lengths, the traveled distance is equal to X.