[LeetCode] Linked List Cycle

 

 

Problem

 

 

---

 

Solution

 

Use two pointers that move with different speeds. One moves forward by steps of 1, and the other moves by steps of 2.

If the faster pointer reaches the end of the list, there is no loop in the list.

If there is a loop in the list, the two pointers will intersect eventually. Return true when that happens.

Check for edge cases where the list is empty or there are less than 3 elements in the list without a loop. In the latter case, while loop should not execute at all.

Space complexity is O(1).

The difference of speed of the two pointers is 1, so it's going to take the cyclic length for the faster pointer to catch up with the slower one. The cyclic length is at most N. Therefore time complexity is O(2N) = O(N) in the worst case.

# 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 head is None:
        	return False
        slowPtr = head
        fastPtr = head.next
        while slowPtr and fastPtr and fastPtr.next:
        	if slowPtr == fastPtr:
        		return True
            slowPtr = slowPtr.next
            fastPtr = fastPtr.next.next
       	
        return False