How to find the previous node of a singly linked list without the head pointer

Question

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.

• Shridhar R Kulkarni: Are you sure about the type of linked list here? May be it is XOR linked list.
• arkham knight: Yes i am sure it was a normal linked list, he specifically said that
• Can Bayar: I know this is not really an answer but I don't think you can find the previous item under these circumstances. :)
• arkham knight: @CanBayar yea i thought the same. When i asked the interviewer he said " think about it " and moved on to the next question
• Jim Mischel: If the only information you have is that this node is part of a singly linked list, then you can't find the parent. Without the head pointer, or a reference to a node that you know is ahead of this one in the list, then it's impossible to find the parent. It would be interesting to hear the interviewer's solution to this problem.

Answer 1

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.

Answer 2

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;
 
}

Answer 3

The ONLY way you can do this is if the linked list is circular, i.e., the last node points to the first node as a type of circular list. Then it is simply a list walk keeping track of the previous node until you arrive again at the node you're on.

Answer 4

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()

• Amit Dwivedi: also, just to mention, this code will delete items only between the first and last data value. If you will try deleting the first value then it will throw and error as its not having any parent node and if you will try to delete the last value then it will get deleted but will throw an exception because that is not having any child node and I have not handled these conditions in my code.