Revision of Loop in list

1 file changed, 36 insertions

loop.cpp(file created)

		@@ -0,0 +1,36 @@
1	+	#include <iostream>
2	+	#include <memory>
3	+
4	+	struct ListNode {
5	+	int val;
6	+	std::shared_ptr<ListNode> next;
7	+	ListNode(int x) : val(x), next(nullptr) {}
8	+	};
9	+
10	+	bool hasCycle(std::shared_ptr<ListNode> head) {
11	+	auto slow = head;
12	+	auto fast = head;
13	+
14	+	while (fast != nullptr && fast->next != nullptr) {
15	+	slow = slow->next;
16	+	fast = fast->next->next;
17	+
18	+	if (slow == fast) {
19	+	return true;
20	+	}
21	+	}
22	+
23	+	return false;
24	+	}
25	+
26	+	int main() {
27	+	auto head = std::make_shared<ListNode>(1);
28	+	head->next = std::make_shared<ListNode>(2);
29	+	head->next->next = std::make_shared<ListNode>(3);
30	+	head->next->next->next = std::make_shared<ListNode>(4);
31	+	head->next->next->next->next = head->next;
32	+
33	+	std::cout << hasCycle(head) << std::endl; // Output: 1 (true)
34	+
35	+	return 0;
36	+	}

Newer Older