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.
You can do it like this.. you can replace the value of current node by value of next node.. and in the next of 2nd last node you can put null. its like delete a element from a string. here is code
void deleteNode(ListNode* node) {
ListNode *pre=node;
while(node->next)
{
node->val=node->next->val;
pre=node;
node=node->next;
}
pre->next=NULL;
}
It is possible. here is the code for your reference.Here, I have assumed that I know the data values of each node. You can test this code by giving 'b' and 'c' in call method. Obviously you can create multiple objects too. Let me know if this is the solution you are looking for.
# Program to delete any one node in a singly link list
class A:
def __init__(self,data):
self.data=data
self.node=None
class B:
def __init__(self):
self.head=None
def printlist(self):
printval=self.head
c=0
self.call(printval,c)
def call(self,printval,c):
temp1=None
temp2=None
while printval:
if printval.data=='c' and c==0:
c=c+1
temp2=printval.node
del printval
temp1.node=temp2
printval=temp1.node
print(printval.data)
temp1 = printval
printval=printval.node
o1=B()
o1.head=A("a")
o2=A("b")
o3=A("c")
o4=A("d")
o1.head.node=o2
o2.node=o3
o3.node=o4
o1.printlist()
