Given a linked list, determine if it contains a cycle. If a cycle is present, find the node where the cycle begins and return it. If there is no cycle, return nullptr.
Table of Contents
Sample Input:
1 -> 2 -> 3 -> 4 -> 5 -> 2 (the 'next' pointer of 5 points back to 2)
Expected Output:
Node with value 2
In this example, the linked list has a cycle, as indicated by the ‘next’ pointer of node 5 pointing back to node 2. The cycle begins at node 2, so the expected output is the node with value 2.
Time and Space Complexity:
The time complexity of the algorithm should be O(n), where ‘n’ is the number of nodes in the linked list. The space complexity is O(1) as we are using a constant amount of additional memory.
Now, let’s provide the C++ solution with comments explaining the code:
#include <iostream>
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* detectCycle(ListNode* head) {
// Use two pointers: slow and fast
ListNode* slow = head;
ListNode* fast = head;
// Initialize a flag to detect if a cycle exists
bool hasCycle = false;
// Traverse the linked list with two pointers
while (fast != nullptr && fast->next != nullptr) {
// Move slow pointer one step at a time
slow = slow->next;
// Move fast pointer two steps at a time
fast = fast->next->next;
// If there's a cycle, the two pointers will meet at some point
if (slow == fast) {
hasCycle = true;
break;
}
}
// If there is no cycle, return nullptr
if (!hasCycle) {
return nullptr;
}
// Reset the slow pointer to the head of the linked list
slow = head;
// Move both pointers at the same pace until they meet again
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
// At this point, the slow pointer and fast pointer will meet at the start of the cycle
return slow;
}
int main() {
// Create the linked list for the sample input
ListNode* node1 = new ListNode(1);
ListNode* node2 = new ListNode(2);
ListNode* node3 = new ListNode(3);
ListNode* node4 = new ListNode(4);
ListNode* node5 = new ListNode(5);
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
node5->next = node2; // Point the last node back to node2, creating a cycle
// Find the node where the cycle begins
ListNode* cycleStart = detectCycle(node1);
if (cycleStart != nullptr) {
std::cout << "Node with value " << cycleStart->val << " is the start of the cycle.\n";
} else {
std::cout << "No cycle found in the linked list.\n";
}
// Don't forget to free the allocated memory
delete node1;
delete node2;
delete node3;
delete node4;
delete node5;
return 0;
}
The detectCycle function is an extension of the “Linked List Cycle” problem. It uses two pointers, slow and fast, to detect if a cycle exists. Once a cycle is found, it resets the slow pointer to the head of the linked list and then moves both pointers at the same pace until they meet again at the start of the cycle.
In the given example, the function will correctly find the node with value 2 as the start of the cycle and return it. The time complexity of this approach is O(n) because in the worst case, both pointers will traverse the entire linked list once. The space complexity is O(1) as we are only using two pointers regardless of the size of the input linked list.