You are currently viewing Check if Linked List has a Cycle | Linked List Cycle | Leetcode 141

Check if Linked List has a Cycle | Linked List Cycle | Leetcode 141

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. 

Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

                    Input: head = [3,2,0,-4], pos = 1
                    Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

  • The number of the nodes in the list is in the range [0, 104].
  • -105 <= Node.val <= 105
  • pos is -1 or a valid index in the linked-list.

Using a Set

We will traverse through the linked list using current pointer. While traversing we will use a set() to store the addresses(current.next) of the nodes. We will also check if the current.next already exists in the set or not. If it exists we will return True else we return False.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # creating a set
        node_set = set()
        
        # Traversing through the list
        current = head
        while(current):
            if current.next not in node_set:
                node_set.add(current.next)
            else:
                return True
            current = current.next
        return False

Time Complexity: O(N)
Space Complexity: O(N),since we are using a set.

Using two pointers : Floyd’s Cycle Finding Algorithm

Floyd’s cycle finding algorithm is a pointer algorithm that uses two pointers, one moving twice as fast as the other one. The faster one is called the fast pointer and the other one is called the slow pointer. This algorithm is used to find a loop in a linked list.

While traversing the Linked List, if the fast pointer reaches the end (NULL) this shows that there is no loop in the linked list. Else, if the Fast pointer again catches the slow pointer at some time, then a loop exists in the linked list.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head
        while (slow != None and fast != None and fast.next != None):
            slow= slow.next
            fast = fast.next.next
            
            if (slow == fast):
                return True
        return False

Time Complexity: O(N)
Space Complexity: O(1), since constant space.

Tags: ,