Does everyone solved it with O(n) complexity?

Question

My code is O(n²) and was told time exceeded.

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

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.

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.

---

Seems your comment is an answer. Please detail it like adding your code with some comment. Then post it as an answer! Thanks!

---

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

---

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

---

Yes, I am the admin.

---

Those code you saw had been modified from the original after i asked this question. My first code is that i compare the current node to all previous nodes to see if there is a match every time before step forward to the next. That would be 100% correct to verify the cycle only O(n2)

---

Correct me if I don't understand the problem correct. If there is any with node->next==null, then there is no cycle in the list, right? And the complexity is O(n).

---

Yes, you can consider the problem like it. The key point is how to go over all nodes in the list and check there is no node which node->next == null, since if you just always go next, there is a forever loop.

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.

---

So impressive!

---

Suppose there is a cycle in the list, is there any change that the fast pointer can never catch up the slow pointer?

My concern is that the fast pointer runs two steps each time while the slow pointer does one, and the former might jump over the latter and miss the catch up point.

---

If there is a cycle in the linked list, fast pinter will eventually collide with slow one. The distance between two pointers decreases by one at one time. So what you are worried about will never happen. :)

Answer 2

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

Comments

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.

---

Please add some comment in your code, or just detail your answer about your thought. You can remove your comment here, just write it in your answer.

---

BTW, please edit your code format.

---

Thanks .... .

---

distance<head, begin of cycle> = distance+unknown times of loop size

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

---

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

---

Can you prove the statement " 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 " ?

I don't think it's a valid statement

---

The true statement is: The node where two runners meet is K nodes away from the beginning of the cycle, which is m times cycle's length minus the distance between the head and the beginning of the cycle.

---

That makes sense, saga0086. In fact this can be proved mathematically. Assuming the distance between head and the beginning of the cycle is a, the meeting point from the beginning of the cycle is b, and the length of the cycle is k,

2(a+b) % k = (a+b) % k

therefore (a+b) % k = 0

Answer 3

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;
        ListNode* bak = head;
        while(head!=NULL){
            head = head->next;
            count ++;
            if(head==bak)return true;
            if(!(count&(count-1)))bak = head;
            }
        }
        return false;

    }

Comments

Your solution is interesting. But I am wondering what the time complexity? what is the worse case?

---

Eh..here is a not-so-explicit one: this method will finish soon after

1,"bak" is inside theloop

2,count of "bak",which is 2^k, is greater than the size of the loop

The worst case happens when one of them failed, but there are only a few steps away from satisfying 1and2,say 2^k+3. I still have to wait until 2^(k+1) to get a new "bak". think about 1,2,3,4,5,6,7,8,9,10(loop to 9),which i have to count at least to 16

So i guess it's upper-bounded by 2*n however,you can pick any accelerating sequence to replace i =1,2,4,8.... which would allow for smaller granularity

---

Thanks. I think it is clear for me! So the time cost is O(N) maybe multiple constant due to the cycle length, but it is always O(N), right?

Answer 4

Another solution.

Traverse the list , and if I find a node point to itself, it means the list has a cycle.

Otherwise, I will make the checked node point to itself.

But I break the list,it is just an idea.

class Solution {
public:
bool hasCycle(ListNode *head) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    ListNode *tmp;
    while(head!=NULL){
        if(head->next == head) return true;
        tmp=head->next;
        head->next=head;
        head=tmp;
    }
    return false;
}
};

Comments

Wow... I did this too... And code is accepted. It's an absolutely O(n) solution, but now I'm afraid we cannot modify the list in any way.

---

Yeah....I think so.

Answer 5

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!

---

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 2³⁰? Then your code is incorrect.