3 ms·
Disagree that this problem never arises if you're not implementing a linked list data structure. Here's a file a customer sent you that describes their organiz
by jameshart 12y ago
Disagree that this problem never arises if you're not implementing a linked list data structure.
Here's a file a customer sent you that describes their organizational hierarchy:
ID Name Manager
1 Alice 4
2 Bob 1
3 Charlie 8
4 Dave -
5 Elise 3
6 Fred 2
7 Gemma 1
8 Henry 5
Is this a valid hierarchical tree? Okay, it's not exactly the same problem, but it's certainly similar...
- phaedrus 12y agoTechnically in the context of an org hierarchy that would be detecting cycles in a directed graph, not a linked list cycle. I don't think the algorithm to detect cycles in a linked list applies to general graph problems, and the problem is much harder for graph cycles.
- jameshart 12y agoIt's not a generic directed graph either, though - each node only has one outbound link. The sequence of parents for any given node is a linked list, and a cycle in that list is invalid. You certainly don't need to run tortoise and hare for every node path looking for cycles. There are other approaches, clearly - reachability analysis starting from each root node, for example. But if I were to ask you to write a routine to find the root node for a given node based on that data, then ask you to guard that routine against finding yourself in an infinite loop or stack overflow, tortoise and hare would be a legitimate answer. Just trying to make it clear that just because the question asks about linked lists, doesn't mean it's always about abstract data structures.