0% completed
I understand how to iterate among a linked list.I don't understand why this is t...
Ray
Jan 15, 2022
I understand how to iterate among a linked list.
I don't understand why this is the best approach? It works though.
Given the example (6 long list, cycle length of 4, cycle starting from 3rd node):
The solution is to calculate cycle length, then start over from head, have pointer 2 move cycle length, and then find when pointers 1 & 2 meet.
Could an alternate approach work where you: 1.) find the first cycle node (slow node when slow === fast), 2.) start from head and count 1 by 1 until you reach the first cycle node?
I tried this alternative, but my code gives me 5 instead of 3 for the 1st part. The other 2 parts work (with expected 4 & 1 nodes).
0
0
Comments
Interviews 4 years ago
This is a bad approach. Better to find intersection of the fast and slow pointer using code from LinkedList Cycle (easy), then set ptr2 to the node at the intersection, and ptr1 to the head node, then iterate both until they meet.
Athanasios Petsas4 years ago
Haha, yeah that's what I did the first time I tried to solve this problem. It seems that fast and slow pointers will meet right at the node that is cycle-length away from the head! At that point fast will be exactly as many nodes away from the start of the cycle as is t...