Java O(n) time constant space solution


  • 0

    Idea: Use slow and fast pointers, which move one and two unit(s) ahead each time respectively. If a circle does not appear in the list, the fast pointer will finally reach null (or its next reaches null). Other wise, there must be some time that the slow pointer catches up with the fast one.

    public class Solution {
        public boolean hasCycle(ListNode head) {
            if (head == null) return false;
            
            ListNode slow = head;
            ListNode fast = head;
            
            while (fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                
                if (fast == null) return false;
                if (slow == fast || slow == fast.next) return true;
            }
            
            return false;
        }
    }
    

Log in to reply
 

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