Leetcode 141: Linked List Cycle

Linked List Cycle

https://leetcode.com/problems/linked-list-cycle/

Naive: O(N) space, O(N) time

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return False
            
        dic = {id(head): True}
        
        while head.next is not None:
            head = head.next
            if dic.get(id(head), None):
               return True
            else:
                dic[id(head)] = True
        return False 
        

 

Use two pointers (one fast, one slow). The distance between them will increase from 0 to at most half of the length of the list, as the slow point traverses the linked list one node by one node. If there is a loop, the fast pointer will eventually meet with the slow pointer.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return False
        
        slow_p = fast_p = head
        while fast_p and fast_p.next:
            slow_p, fast_p = slow_p.next, fast_p.next.next
            if slow_p is fast_p:
                return True
        return False