Critique my Python solution, O(n) I think, and constant space


  • 3
    E

    If I traverse the linked list and it has a cycle, the next attribute will never result in none. My idea is that two conditions exist:

    Condition 1) I find None, which means no cycle exists so I return False.

    Condition 2) I do not find None.

    To test for condition 2 I have created a slow pointer. If the slow pointer move at any fraction of the speed of the fast pointer, the fast pointer will eventually catch it. Even when the cycle is a short cycle located at the end of a long list, my slow pointer will eventually enter the cycle and be caught. By using a slow pointer moving at half the speed of the fast pointer, my run should take at most, (3n)-1 next operations (I think). Which means I'm bound O(n).

    class Solution:
        # @param head, a ListNode
        # @return a boolean
        def hasCycle(self, head):
            slow = head
            fast = head
            counter = 0
            while fast is not None:
                # Make the slow pointer walk
                counter += 1
                if (counter%2) == 0:
                    slow = slow.next
                
                if fast.next == slow:
                    return True
                fast = fast.next
            return False

  • 0
    D

    We got the same idea.
    JAVA version:

    public class Solution {
        public boolean hasCycle(ListNode head) {
            if (head==null)
                return false;
            ListNode p1, p2;
            p1 = head;
            p2 = head;
            while(true)
            {
                for (int i = 0; i<2; i++)
                {
                    if (p1.next==null)
                        return false;
                    else
                        p1 = p1.next;
                    
                    if (p1==p2)
                        return true;
                }
                if (p2.next==null)
                    return false;
                else
                    p2 = p2.next;
            }
        }
    }

  • 4
    G

    You don't need a counter. You can just keep following .next. Here is my python code:

    class Solution:
        # @param head, a ListNode
        # @return a boolean
        def hasCycle(self, head):
            slow = fast = head
            while slow and fast and fast.next:
                slow = slow.next
                fast = fast.next.next
                if slow == fast:
                    return True
            return False

Log in to reply
 

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