Daily LeetCode Problems: Problem 141. Linked List Cycle

Cracking the Cycle Code: Detecting Linked List Cycles

Introduction:

Welcome to another exciting problem-solving article! Today, we’ll explore problem 141 from LeetCode: “Linked List Cycle”. This problem focuses on determining whether a linked list contains a cycle. We’ll dive into the problem statement, devise a strategy, analyze complexity, and provide a step-by-step solution.

Problem Statement:

We are given the head of a linked list. Our task is to determine if the linked list contains a cycle. A cycle exists in a linked list when a node can be reached again by continuously following the next pointer. The variable pos internally denotes the index of the node where the tail's next pointer is connected to. We do not receive pos as a parameter. Our goal is to return True if a cycle exists and False if the linked list is cycle-free.

Approach:

To solve this problem, we’ll use the concept of two pointers. We’ll initialize two pointers, one slow (moves one step at a time) and one fast (moves two steps at a time). If a cycle exists, the fast pointer will eventually catch up to the slow pointer. If there is no cycle, the fast pointer will reach the end of the list.

Pseudocode:

def hasCycle(head):
    if not head or not head.next:
        return False
    
    slow = head
    fast = head.next
    
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    
    return True

Complexity Analysis:

Let’s analyze the complexity of our solution:

• Time complexity: Both pointers traverse the list at different speeds, resulting in a time complexity of O(n), where n is the number of nodes in the list.
• Space complexity: We use two pointers, resulting in a space complexity of O(1).

Step-by-Step Solution:

1. Check if the linked list is empty or contains only one node (no cycle can exist in such cases). If true, return False.
2. Initialize two pointers, slow and fast, to the head and the node after the head, respectively.
3. Enter a while loop that continues until slow and fast pointers meet (indicating a cycle) or fast reaches the end of the list (indicating no cycle).
4. Within the loop:

• Check if fast or fast.next is None (to avoid errors when moving fast two steps at a time). If true, return False.
• Move slow one step forward and fast two steps forward.

1. If the loop terminates because slow and fast meet, return True (a cycle exists).
2. If the loop terminates because fast reaches the end of the list, return False (no cycle exists).

Full Solution

Python

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

class Solution:
  def hasCycle(self, head: ListNode) -> bool:
    slow = head
    fast = head

    while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
      if slow == fast:
        return True

    return False

Java

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
  public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow == fast)
        return true;
    }

    return false;
  }
}

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
 public:
  bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
      slow = slow->next;
      fast = fast->next->next;
      if (slow == fast)
        return true;
    }

    return false;
  }
};

Conclusion:

In this article, we cracked the code on detecting cycles in a linked list by using the two-pointer approach. We learned how to efficiently determine whether a linked list contains a cycle or not. Understanding the problem statement and applying our approach will help you identify cycles in linked lists with ease. Happy coding!