# My O(n) solution without using extra space:cut the ring into two "rail"

• Hey! I've found a solution with O(n) time complexity and O(1) space complexity. My method is very simple with the follow steps:

1. Find a ring point via "fast and slow running" method.if there isn't a node like that,then return NULL;
2. Cut the ring at the ring point found before,making the cycle link list like two rails with different start points jioning together.
3. Make the two "rails" the same length.
4. search the two "rails" the same time,and compare the two nodes,if they are equal,return one which is the answer .

my code:

``````	ListNode *detectCycle(ListNode *head) {
ListNode * p1,* p2,* p3;
int m = 0;
return NULL;
while(true)      //find a ring node using "fast and slow" method
{
if(p1 == p2)     //if find the ring node,cut the ring at this node.
{                // It like two rails with different start point jioning together.
p2 = p1->next;  //make p2 the front node of the cut node,in other word the second rail's start point.
//head is the first rail's start point.
p1->next = NULL; //make the cute node's next NULL.
p3 = p1;
while(p3)        //this code's purpose is to make the two rails  the same length.
{
p3 = p3->next;
m++;
}
p3 = p2;
while(p3)
{
p3 = p3->next;
m--;
}
if(m>=0)
while(m--)
p1 = p1->next;
else
while(m++)
p2 = p2->next;

while(p1&&p2)		//search the two rails in the same time;
{
if(p1 == p2)   //the first equal node is the begin node of the cycle
return p1; //return the node.
p1 = p1->next;
p2 = p2->next;
}
}
if(p1->next)
p1 = p1->next;
else
return NULL;
if(p2->next&&p2->next->next)
p2 = p2->next->next;
else
return NULL;
}
return NULL;
}``````

• The idea is good, but does this method change the original list? Sometimes we are not allowed to change the original one.
However, if we are allowed to change it, there will be many O(1) space complexity algorithms such as changing the 'val'.

• Actually,we don't need to change the original list.The key point of this method is to find a ring node, and then search concurrently from this ring node and the start node of the list. If there is a ring, they will meet at the start node of the ring.

• Hi, the idea of 'fast and slow' is cool!! I use your idea and simplify the code. First the 'fast and slow' method is used to find the size of the cycle (its multiples but it doesn't matter). Then search from the head again using two pointer which distance is the size. The first node they meet is the start point of the cycle. If there is no cycle, it will occur exception, so I return none at catch block.

Here is my code.

``````class Solution:
# @return a list node
try:
# Find the size of the cycle
size = 1
while ptr1 != ptr2:
ptr1 = ptr1.next
ptr2 = ptr2.next.next
size += 1

# Let ptr2 is size step front of ptr1
for i in range(size):
ptr2 = ptr2.next

# Move two pointer at the same speed,
# and they will meet at the start of the ring.
while ptr1 != ptr2:
ptr1 = ptr1.next
ptr2 = ptr2.next
return ptr1

except:
# If there is no cycle, then 'NoneType' exception occurs.
return None``````

• wow! I got the exact same solution with you! Your description is really expressive.

Here is my Java edition:

``````public class Solution {
while(fastNode != null && slowNode != null){
slowNode = slowNode.next;
fastNode = fastNode.next;
if(fastNode == null)
return null;
fastNode = fastNode.next;

if(fastNode == slowNode && fastNode != null){
/**
* yes, we got the circle. Let's find the node where the cycle
* begins.
*/
}
}
return null;
}

private ListNode findBeginningCycleNode(ListNode head1, ListNode nodeInCycle) {
nodeInCycle.next =  null; // break the cycle
}

if(len1 > len2)
for(int i = 0; i < len1 - len2; i++)
else
for(int i = 0; i < len2 - len1; i++)

while(true){
}
}