Menu
I read some interview question online about how would you find if there's a loop in a linked list, and solution (Floyd's cycle-finding algorithm) is to have two pointers, one is 2x faster than the other, and check if they meet again.
My question is: Why can't I just keep one pointer fixed, just move the other pointer forward by 1 step each time?
208
Step 1: Move 'S' to the start of the list, but 'F' would remain point to node 3. Step 2: Move 'S' and 'F' forward one node at a time until they meet. Step 3: The node where they meet is the start of the loop. Let's visualize the above algorithm for more clarity.
Write a function findFirstLoopNode() that checks whether a given Linked List contains a loop. If the loop is present then it returns point to the first node of the loop. Else it returns NULL.
A simple solution is to use hashing. The idea is to traverse the given list and insert each encountered node into a set. If the current node already presents in the set (i.e., it is seen before), that means a cycle is present in the list.
Method 2 (Better Solution) Let the count be k. Fix one pointer to the head and another to a kth node from the head. Move both pointers at the same pace, they will meet at the loop starting node. Get a pointer to the last node of the loop and make the next of it NULL.
Because maybe not the complete linkedList is within the loop.
For a linked list lasso detection algorithm, you need two pointers:
As long as the first pointer is where the cowboy is, no loop is detected. But if you move it stepwise forward, it will eventually enter the loop.
BTW, lasso is the terminus technicus from graph theory, cowboy isn't.
61
Because the first (non-moving) pointer might not lie within the loop, so the pointers would never meet. (Remember that a loop may consist of only part of the list.)
30
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
