anduin hat die Gist bearbeitet . Zu Änderung gehen
1 file changed, 36 insertions
loop.cpp(Datei erstellt)
| @@ -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 | + | } | |
Neuer
Älter