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

**My initial thoughts:**

We need to consider two cases: if that node is the head, then we need to update head pointer to the next one. If that node is in the middle, then we need to update the previous pointer.

**My initial codes:**

public static void deleteANode(LLNode head, LLNode item) {
if (head == item) {
head = item.getNext();
item.setNext(null);
return;
}
LLNode previous = head, current = head;
while (current != null) {
if (current == item) {
previous.setNext(current.getNext());
current.setNext(null);
return;
} else {
previous = current;
current = current.getNext();
}
}
return;
}

**Comments after running:**

- It works fine with O(n) time complexity and O(1) space complexity.
- After reading the solution, I found out that the question explicitly specifies that only the access to that node is given therefore you don’t know the head pointer.

**Solution:**

public static void deleteNode(LLNode node) {
if (node == null || node.getNext() == null)
return;
LLNode nextNode = node.getNext();
node.setData(nextNode.getData());
node.setNext(nextNode.getNext());
nextNode.setNext(null);
}

Comments:

- If that node happens to be at the end, then there’s no way to delete it without knowing the previous node.

### Like this:

Like Loading...

*Related*

under the hood

Oct 10, 2012@ 02:07:54In fact for the solution, it’s okay if the node happens to be at the end, because with proper implementations of linked lists (whether singly or doubly), the head and tail are usually set to be null Nodes, or so called dummy nodes.

So if the given node is the last node (before dummy tail), then what the solution does is to set node as the dummy tail, with the assumption that setData() and setNext() methods would actually take care of the edge case itself.

(btw, some of the book solutions are horrible)

vikram

Dec 23, 2012@ 11:31:04Hey

Thanks for the solution, but I am confused by the statement which says “given only access to that node”. I do not understand what it means. I would really appreciate if you can put some light on that.

kinshuk4

May 08, 2014@ 18:55:46I liked your solution. This is really a good trick question. Here is my post on same topic – http://k2code.blogspot.in/2010/10/deleting-middle-node-from-single-linked.html. Happy posting 🙂