Delete a node in a singly linked list given only access to that node

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.
Advertisements

3 Comments (+add yours?)

  1. under the hood
    Oct 10, 2012 @ 02:07:54

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

    Reply

  2. vikram
    Dec 23, 2012 @ 11:31:04

    Hey
    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.

    Reply

  3. kinshuk4
    May 08, 2014 @ 18:55:46

    I 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 🙂

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: