We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Your code get segfault cause the i variable goes outside the visited array size.
The idea of keeping track of visited nodes is correct, but using an incrementing counter not linked to a specific node of the list is wrong.
If you decide to employ an array, you have some possibilities:
Store the current node address in the array. For each node of the list, check in the array if its address is there. If not, add it. Complexity is O(n^2).
Use a hash tabl. The hashing function input is the node address, the output is an array offset. You'll still need to store node addresses (as the key) to handle hash collisions though. Best case complexity is O(n), worst case is O(n^2)).
Linked Lists: Detect a Cycle
You are viewing a single comment's thread. Return to all comments →
Your code get segfault cause the i variable goes outside the visited array size.
The idea of keeping track of visited nodes is correct, but using an incrementing counter not linked to a specific node of the list is wrong.
If you decide to employ an array, you have some possibilities: