Does everyone solved it with O(n) complexity?

Question

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

Comments

Could please detail your solution and your analysis about the time complexity of your solution? It will help others see what might block you.

---

i define a variable called flags ,flags is a big number,(ie flags=2^31)

then iterate from the head node... then let the value of node which had iterated be flags ....so when i find the value of the current node is falgs ...that means the list has a cycle

Answer 1

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.

Comments

Great, I never thought about this before.

---

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

Answer 2

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*

Answer 3

public static int nil=(int)Math.pow(2, 30);
public boolean hasCycle(ListNode head) {
        if(head==null)
        return false;
    ListNode temp=head;
    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;
}

Comments

Could you please update your answer with some words to tell your brief idea? Like your comment on the question? Please do not answer a question thru its comment, just give a answer. Thanks!