Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e
Approach:
Lets say the list is a->b->c->d->e
We have point p1 pointing to "c" node.
Get a pointer p2 to point to the next node of p1 ie to node "d" here.
Now copy "d" node data to node pointed by p1 and delete node pointed by p2.
new list is "a->b->d->e";
NOTE: this problem can not be solved if pointer p1 is pointing to the last node of the singly linked list.
Liked your post. Here is my post on the same - http://k2code.blogspot.in/2010/10/deleting-middle-node-from-single-linked.html and basic idea:
ReplyDeleteGiven the linked list being :
-> Node(i-1) -> Node(i) -> Node(i+1) -> ... and we need to delete Node(i).
1. Copy data (not pointer, the data itself) from Node(i+1) to Node(i), the list will look like: ... -> Node(i-1) -> Node(i+1) -> Node(i+1) -> ...
2. Delete the second Node(i+1), it doesn't require pointer to the previous node.