Here's an interesting problem for you guys. Before anyone starts, this is *not* homework; I first solved it half a year ago or so.
The setup:
I'll give you a pointer to the head node of a linked list. Suppose the list is set up as in C, so you can access the pointer value directly if you want to. (i.e. the implementation is not hidden as in Java)
The problem is then to tell me if the linked list has a cycle. A cycle means that at some point, a node points to a previous node. This means that the "last" node points to say itself, the first node, the fifth node, or wherever. (Point is that it is not just the last node pointing to the first node).
Notes:
>You DO NOT know how long the list is.
>You cannot edit the list--no changing pointers for example. I spent years making the list, and there is not enough HD space on earth to make a copy. Yeah... right.
>It is a singly-linked list.
I'll go ahead and give you the worst solution:
Use a pointer to march through the list and build an array of pointer values as you go. At each step, compare the current value to the entire array to see if you've been there before.
You can do better than that.
Edit: if this is a well-known problem, don't share the answer if you've seen it before. I'm not a CS major so I have no idea
The setup:
I'll give you a pointer to the head node of a linked list. Suppose the list is set up as in C, so you can access the pointer value directly if you want to. (i.e. the implementation is not hidden as in Java)
The problem is then to tell me if the linked list has a cycle. A cycle means that at some point, a node points to a previous node. This means that the "last" node points to say itself, the first node, the fifth node, or wherever. (Point is that it is not just the last node pointing to the first node).
Notes:
>You DO NOT know how long the list is.
>You cannot edit the list--no changing pointers for example. I spent years making the list, and there is not enough HD space on earth to make a copy. Yeah... right.
>It is a singly-linked list.
I'll go ahead and give you the worst solution:
Use a pointer to march through the list and build an array of pointer values as you go. At each step, compare the current value to the entire array to see if you've been there before.
You can do better than that.
Edit: if this is a well-known problem, don't share the answer if you've seen it before. I'm not a CS major so I have no idea