InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
How To Remove Loops In A Linked List (or) What Are Fast And Slow Pointers Used For? |
|
Answer» The best SOLUTION runs in O(N) time and uses O(1) space. This method uses two pointers (ONE slow POINTER and one fast pointer). The slow pointer traverses one node at a time, while the fast pointer traverses twice as fast as the first one. If the linked list has loop in it, eventually the fast and slow pointer will be at the same node. On the other hand, if the list has no loop, OBVIOUSLY the fast pointer will reach the end of list before the slow pointer does. HENCE we detect a loop. The best solution runs in O(N) time and uses O(1) space. This method uses two pointers (one slow pointer and one fast pointer). The slow pointer traverses one node at a time, while the fast pointer traverses twice as fast as the first one. If the linked list has loop in it, eventually the fast and slow pointer will be at the same node. On the other hand, if the list has no loop, obviously the fast pointer will reach the end of list before the slow pointer does. Hence we detect a loop. |
|