Floyd's Cycle Finding Algorithm - The Best Way to Find a Cycle in a Linked List скачать в хорошем качестве

Floyd's Cycle Finding Algorithm - The Best Way to Find a Cycle in a Linked List

Floyd's cycle finding algorithm allows you to detect a cycle in a linked list, and return the entry point of the cycle, in O(n) time and O(1) space. Code: https://gist.github.com/emcapsulation... 0:00 Introduction 0:42 Hashset Method 1:30 Algorithm Walkthrough 2:41 Large Example 3:10 Explanation 5:44 Code Algorithm Steps 1. Initialise a slow pointer (tortoise) and fast pointer (hare) pointing to the head of the linked list. 2. Do while the hare and tortoise have not met: 2a. If the hare reaches NULL, there is no cycle. 2b. Step the tortoise one node forward. Step the hare two nodes forward. 3. If the tortoise and hare meet (both pointers point to the same node), there is a cycle in the linked list. If so: 3a. Take the tortoise back to the head of the linked list. 3b. Step both the hare and tortoise pointers one node at a time. 4. They will meet at the start of the cycle, so return the pointer to that node.