141. Linked List Cycle#

Difficulty: Easy

Link to Problem: To see the Linked List Cycle problem on LeetCode, click here!

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.

Constraints:

  • The number of the nodes in the list is in the range \([0, 10^4]\).

  • \(-10^5\) <= Node.val <= \(10^5\)

  • pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using \(O(1)\) (i.e. constant) memory?

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

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

Explanation:#

The given code defines a class Solution with a method hasCycle for determining if a linked list has a cycle.

The ListNode class represents nodes in the linked list, where each node has a val (a value associated with the node) and a next attribute (a reference to the next node in the list).

The hasCycle method takes the head of a linked list as input and returns True if there is a cycle in the linked list, and False otherwise. It uses two pointers, slow and fast, to traverse the linked list. If there is a cycle, the fast pointer will eventually catch up to the slow pointer.

The algorithm works as follows:

  1. It checks if the input head is None (an empty list). If it is, the method returns False because an empty list can’t have a cycle.

  2. Two pointers, slow and fast, initially point to the head of the list.

  3. The code enters a while loop where fast moves two steps at a time, and slow moves one step at a time.

  4. If there is a cycle, fast will eventually catch up to slow, and the method returns True.

  5. If the loop completes without finding a cycle, the method returns False.

# Helper function to create a linked list with a cycle
def create_linked_list_with_cycle(values, pos):
    dummy = ListNode()
    current = dummy
    cycle_node = None
    
    for i, val in enumerate(values):
        current.next = ListNode(val)
        current = current.next
        
        if i == pos:
            cycle_node = current
    
    if cycle_node:
        current.next = cycle_node
    
    return dummy.next

This helper function is designed to create a linked list with a cycle for testing purposes. It takes two arguments:

  1. values: A list of values representing the nodes in the linked list.

  2. pos: An integer representing the index of the node where the cycle begins.

Here’s how the function works:

  • It starts by creating an empty ListNode called dummy. This dummy node is used to simplify the creation of the linked list.

  • It initializes a current pointer to the dummy node. This pointer will be used to traverse the linked list.

  • It initializes a cycle_node variable to None. This variable will hold the reference to the node where the cycle begins, if any.

  • It then iterates through the values list, creating a new ListNode for each value and appending it to the linked list.

  • Inside the loop, it checks if the current index i is equal to the specified pos. If they match, it sets cycle_node to the current node. This simulates the creation of a cycle in the linked list.

  • After the loop, if cycle_node is not None (indicating a cycle should be created), it connects the last node in the linked list to cycle_node, effectively creating a cycle.

  • Finally, it returns the reference to the first node of the linked list (not the dummy node).

This helper function allows you to easily create test cases where you can specify the values for the linked list and the position where the cycle starts. It’s particularly useful for testing the code’s ability to detect cycles in linked lists.

Test cases#

### Example 1
head = [3,2,0,-4]
pos = 1

head = create_linked_list_with_cycle(head, pos)
solution = Solution()
result = solution.hasCycle(head)
print(result)

True

### Example 2
head = [1,2]
pos = 0

head = create_linked_list_with_cycle(head, pos)
solution = Solution()
result = solution.hasCycle(head)
print(result)

True

### Example 3
head = [1]
pos = -1

head = create_linked_list_with_cycle(head, pos)
solution = Solution()
result = solution.hasCycle(head)
print(result)

False

Let’s discuss the time and space complexity of the code for detecting a cycle in a linked list:

Time Complexity:

The time complexity of this code is \(O(n)\), where “\(n\)” is the number of nodes in the linked list.

The reason for this is that both the slow and fast pointers traverse the linked list, and they move at different speeds. In the worst case, when there is no cycle, the fast pointer will reach the end of the list after going through approximately \(n/2\) nodes. In the case of a cycle, it may take some extra iterations for the fast pointer to catch up to the slow pointer. However, the total number of iterations is still proportional to the number of nodes in the linked list, making it \(O(n)\).

Space Complexity:

The space complexity of this code is \(O(1)\), which means it uses constant space.

The reason for this is that regardless of the size of the linked list, the code only uses two additional pointers (slow and fast) to traverse the list. These pointers do not depend on the size of the input linked list, so the space complexity remains constant.

In summary, this code efficiently detects cycles in a linked list with a time complexity of \(O(n)\) and a space complexity of \(O(1)\). It is an example of an algorithm that solves a complex problem with minimal memory usage.