Hi this was an interview question, Any suggestions/answers would be appreciated.
In the question : He gave me a singly linked list and pointed out at a random node and asked me to find the previous node. I asked if i have access to the head pointer , he said no. I asked if it was a circular or double linked list, he again said no. How would i find the previous node?
P.S. - I do not have access to the head pointer at all, so i can't keep track of previous pointer.
From a purely CS standpoint, if you construct a non-cyclic singly linked-list of length n as:
L1 -> L2 -> ... -> L(x-1) -> Lx -> ... -> Ln
The following theorem holds true:
Theorem: Node Lx can only be reached by nodes L1 through Lx.
Just by looking at it, this is fairly obvious: there is no going backwards. I skipped over some steps, but this is a fairly easy conclusion to make. There is no path from Lx to previous nodes in the chain. A formal proof would use induction. This page explains how one might perform induction over a linked list.
The contrapositive is: Nodes L1 through L(x-1) cannot be reached by node Lx. As a direct result L(x-1) cannot be reached by node Lx which contradicts the claim by the interviewer. Either the interviewer is wrong or your interpretation of the interviewer is wrong.
I was only given the random node and i was asked to find the previous node, no head pointer, no cycles
If such a thing were possible, it would break many existing applications of computer science. For example, Garbage Collection in safe languages like Python or Ruby relies on nodes no longer being reachable once there is no path to them. If you were able to reach a node in this way, you could cause a "use after freed" bug making the language unsafe.
The interviewer might have expected you to state the question is impossible. I have had interviews where this is the case. Sometimes, the interviewer is probing for a more "creative" solution. For example, in a language like C++, all the nodes may be stored in an underlying resource pool which can be iterated over to find the previous node. However, I would find this implementation unusual for an interview and in practice.
Needless to say, the problem as you have stated is not possible under the given constraints.