Detect a loop in a linked list
Given a linked list, write a program to return the start of the loop if a loop exists in that list in O(n) time and O(1) space.
This video explains the floyd's algorithm and its proof of correctness.
1. Initialize two references: a slow reference 'S' and a fast reference 'F' to the start of the list
2. Move 'S' forward one node at a time and move 'F' forward two nodes at a time.
3. If at some point of time, reference 'S' and reference 'F' point to the same node of the list then we know that there is a loop in the list otherwise we return null saying there is no loop.
4. After the loop is detected in step #3, we move back reference 'S' to the start of the list again and keep 'F' at same meeting point.
5. Now this time around, we move both 'S' and 'F' forward one node at a time until they meet.
6. The node where they meet is start of the loop.
Code: http://www.ideserve.co.in/learn/detect-a-loop-in-a-linked-list
Website: http://www.ideserve.co.in
Facebook: https://www.facebook.com/IDeserve.co.in
Видео Detect a loop in a linked list канала IDeserve
This video explains the floyd's algorithm and its proof of correctness.
1. Initialize two references: a slow reference 'S' and a fast reference 'F' to the start of the list
2. Move 'S' forward one node at a time and move 'F' forward two nodes at a time.
3. If at some point of time, reference 'S' and reference 'F' point to the same node of the list then we know that there is a loop in the list otherwise we return null saying there is no loop.
4. After the loop is detected in step #3, we move back reference 'S' to the start of the list again and keep 'F' at same meeting point.
5. Now this time around, we move both 'S' and 'F' forward one node at a time until they meet.
6. The node where they meet is start of the loop.
Code: http://www.ideserve.co.in/learn/detect-a-loop-in-a-linked-list
Website: http://www.ideserve.co.in
Facebook: https://www.facebook.com/IDeserve.co.in
Видео Detect a loop in a linked list канала IDeserve
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
Detect loop in linked list(floyd algo / Tortoise and hare algo)Find merge point of two linked listWhy Floyd's cycle detection algorithm works? Detecting loop in a linked list.Segregate Even And Odd Nodes in a Linked ListInterview Question: Start of Loop in a Linked ListAlgorithms: Bit ManipulationHow I Got Good at Algorithms and Data StructuresLinked list in Java - 72: Rearrange a linked list in zig-zag mannerFinding loops/cycles in a linked listLecture 1: Algorithmic Thinking, Peak FindingHow to use Cracking The Coding Interview EffectivelyReverse a linked list using recursionClone A Linked List (With Random Pointers) - Linear Space Solution & Tricky Constant Space SolutionPuzzles & Programming Problems (Think Like a Programmer)Reverse a Single Linked ListKadane's Algorithm - Maximum Sum Subarray (Amazon Coding Interview Question)LeetCode 92 | Reverse Linked List IICheck if the singly Linked List is a PalindromeHow to Crack a Google Coding Interview - An Ex-Googler’s Guide