Java 1ms solution without extra space


  • 5

    public boolean hasCycle2(ListNode head) {

    	if(head == null || head.next == null) {
    		return false;
    	}
    	
    	ListNode node = head;
    	while(node != null) {
    		
    		if(node.next == head) {
    			return true;
    		}
    		
    		ListNode temp = node.next;
    		node.next = head;
    		node = temp;
    	}
    	
    	return false;
    }

  • 0
    C

    I don't get this. When the loop runs the first time, node.next = head, then you check node.next == head. In my understanding, this will always be true.

    Also, you never change head, how can you check if there is a circle which don't starts with this head?


  • 1

    I want to let the every node's next node reference to head node. It's just set a flag on every node.
    if there doesn't has cycle, there the last node is null. return false;
    but if there has cycle, I will find it via the flag which next node is head node.

    this is another version. I use empty node to flag, it's more easier to understand.

    public boolean hasCycle(ListNode head) {

        if(head == null || head.next == null) {
    		return false;
    	}
        
        ListNode empty = new ListNode(1);
    	
    	ListNode node = head;
    	while(node != null) {
    		
    		if(node.next == empty) {
    			return true;
    		}
    		
    		ListNode temp = node.next;
    		node.next = empty;
    		node = temp;
    	}
    	
    	return false;
    }

  • 1

    @charlie26

    I want to let the every node's next node reference to head node. It's just set a flag on every node.
    if there doesn't has cycle, there the last node is null. return false;
    but if there has cycle, I will find it via the flag which next node is head node.

    this is another version. I use empty node to flag, it's more easier to understand.

    public boolean hasCycle(ListNode head) {

    if(head == null || head.next == null) {
    	return false;
    }
    
    ListNode empty = new ListNode(1);
    
    ListNode node = head;
    while(node != null) {
    	
    	if(node.next == empty) {
    		return true;
    	}
    	
    	ListNode temp = node.next;
    	node.next = empty;
    	node = temp;
    }
    
    return false;
    

    }


  • 0
    P

    really nice work!


  • 1
    K

    I don't get the "without extra space" meaning, you declare other "ListNode" variables beside "head", then you do use extra space, right? O(1) space is not zero.


  • 0
    C

    Great!!good job


Log in to reply
 

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