Given a node in a singly linked list, and given no other node - not even header, can you delete this node?
Ans.- While deleting a node from a linked list, we need to point 'next' of previous node to the 'next' of current node and make the current node isolated and then free it. With singly linked list, we need to keep track of previous node in order to make above mentioned modifications. This is possible only when header node is provided so that we can traverse the list till this node. As header is not available and the list being singly linked, main point to note is: we can only traverse from the given node in forward direction. This leads us to the solution. We target next node. Copy next node's data to the current node and make current node point to next of next of current node. This way we have removed data to be deleted and next node is isolated in this process, so we then free it up.
Trick- This will not work for all cases. The constraint is in terms of the input. Can you identify it?
Ans.- Think what happens when the given node is the last node in the singly linked list.
No comments:
Post a Comment