Given a linked list, determine if it has a cycle in it. A cycle is when a node in the linked list points to a previously visited node, forming a loop. Return true if there is a cycle, otherwise, return false.
Table of Contents
Sample Input:
1 -> 2 -> 3 -> 4 -> 5 -> 2 (the 'next' pointer of 5 points back to 2)
Expected Output:
true
In this example, the linked list has a cycle, as indicated by the ‘next’ pointer of node 5 pointing back to node 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:
Linked List Cycle C++ solution
#include <iostream>
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
bool hasCycle(ListNode *head) {
// Use two pointers: slow and fast
ListNode *slow = head;
ListNode *fast = head;
// 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) {
return true; // Cycle detected
}
}
return false; // No cycle found
}
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
// Check if the linked list has a cycle
if (hasCycle(node1)) {
std::cout << "The linked list has a cycle.\n";
} else {
std::cout << "The linked list does not have a cycle.\n";
}
// Don't forget to free the allocated memory
delete node1;
delete node2;
delete node3;
delete node4;
delete node5;
return 0;
}
The hasCycle function uses two pointers, slow and fast, to traverse the linked list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle, the fast pointer will eventually catch up to the slow pointer, and they will be pointing to the same node. If there is no cycle, the fast pointer will reach the end of the list (i.e., it will become null) before the slow pointer.
In the given example, the function will correctly detect the cycle and return true. 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.