# Does everyone solved it with O(n) complexity?

• My code is O(n2) and was told time exceeded.

I define a variable called flags, where flags is a big number, (ie: flags=231)

As I iterate the list from head, I change the node's value to be flags. When i found the value of the current node is flags, that means the list has a cycle.

• This is similar with CC150 question. You may try "fast runner and slow runner" solution. Fast pointer runs 2 steps at a time and slow runner runs 1 step at a time. They both start from beginning. If faster runner catches slow runner some time, it means linked list has a circle.

• ``````public class Solution {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
while(fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
if(slow == fast)
return true;
}
return false;
}
}``````

• The node where these two nodes meet is K nodes away from the beginning of the cycle, which is the distance between the head and the beginning node of the cycle, you can find the similar question in Cracking the coding interview.

• Thanks .... .

• This is also my first time hearing about the fast runner slow runner. I shall add it to my toolbox.

• Cool idea of slow/fast pointer !

or you could record the ith(i = 1,2,4,8..........) ListNode* and compare it to your iterating ListNode*

``````   bool hasCycle(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
int count = 0;
count ++;
}
}
return false;

}
``````

• ``````public static int nil=(int)Math.pow(2, 30);
return false;
boolean flags=false;
temp.val=nil;
while(temp.next!=null)
{
temp=temp.next;
if(temp.val==nil)//that means this node has been iterated before, that means the list has a cycle
{
flags=true;
break;
}
else
{
temp.val=nil;
}
}
return flags;
}
``````

• You are not supposed to modify the list, plus one of the node's value could be 231. Anyway, I don't understand how your incorrect solution could be O(n2) complexity, since it is clearly O(n) to me.

• I believe this solution is the same solution @saga0086 mentioned in the question. However, your solution isn't right:

1. You modified the list's value, which is typically not allowed unless explicitly stated.
2. What if one of the node's value is 230? Then your code is incorrect.

= distance<where they meet , begin of cycle>+unknown times of loop size

so,run slow pointer and another pointer from head again, they will meet at the begin of the cycle

• I am wondering how you could edit my question and saw my code. Are you Admin here?

• they will meet at begin of the cycle. but probably not the first time

• Yes, I am the admin.

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