Dare2Solve
Given the head of a linked list, the task is to determine if the linked list contains a cycle. If a cycle exists, return the node where the cycle begins. If there is no cycle, return null
.
To detect a cycle in a linked list, we can use Floyd's Tortoise and Hare algorithm. This algorithm uses two pointers that move at different speeds through the list. If there is a cycle, the fast pointer will eventually meet the slow pointer. To find the entry point of the cycle, we move one pointer to the head and keep the other at the meeting point. Both pointers then move one step at a time until they meet again at the cycle's entry point.
O(N), where N is the number of nodes in the linked list. In the worst case, we traverse the list twice: once to detect the cycle and once to find the cycle's starting node.
O(1), since we only use two pointers and no additional data structures.
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == nullptr) return nullptr;
ListNode *slow = head;
ListNode *fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
while (fast != head) {
head = head->next;
fast = fast->next;
}
return head;
}
}
return nullptr;
}
};
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
while fast != head:
head = head.next
fast = fast.next
return head
return None
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) return null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
while (fast != head) {
head = head.next;
fast = fast.next;
}
return head;
}
}
return null;
}
}
var detectCycle = function(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if(slow === fast) {
while (fast !== head) {
head = head.next;
fast = fast.next;
}
return head;
}
}
return null;
};