Does everyone solved it with O(n) complexity?


  • 7
    D

    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.


  • 0
    S

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


  • 73
    S

    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.


  • 33
    L
    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;
        }
    }

  • 0
    L

    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.


  • 0
    S

    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.


  • 0
    S

    BTW, please edit your code format.


  • 0
    D

    Great, I never thought about this before.


  • 0
    D

    Thanks .... .


  • 0
    N

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


  • 2
    S

    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;
            
        }
    

  • -4
    C
    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;
    }
    

  • 0
    S

    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!


  • 0
    S

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


  • 0

    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.


  • 0

    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.

  • 0
    S

    distance<head, begin of cycle>
    = 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


  • 0
    D

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


  • 0
    D

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


  • 0

    Yes, I am the admin.


Log in to reply
 

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