Linked List Cycle 🧠
LeetCode Link: Linked List Cycle
Difficulty: Easy
Problem Explanation 📝
Problem: LeetCode 141 - Linked List Cycle
Description: Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos, which represents the position (0-indexed) in the linked list where the tail connects to. If pos is -1, there is no cycle in the linked list.
Intuition: To detect if there is a cycle in a linked list, we can use the two-pointer technique. We maintain two pointers, slow and fast. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle in the linked list, the fast pointer will eventually catch up to the slow pointer, and they will meet.
Approach:
- Initialize two pointers, slow and fast, to the head of the linked list.
- Move the slow pointer one step and the fast pointer two steps at a time.
- If there is a cycle, the fast pointer will eventually catch up to the slow pointer.
- If the fast pointer becomes null, there is no cycle in the linked list.
- Return true if the two pointers meet, otherwise return false.
⌛ Time Complexity: The time complexity is O(n), where n is the number of nodes in the linked list. In the worst case, the fast pointer traverses the linked list twice.
💾 Space Complexity: The space complexity is O(1) since we only use two pointers to detect the cycle.
Solutions 💡
Cpp 💻
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;
}
};
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:
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