#CC150 #CC150-chap2 2.3 Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.

DeleteFromList.java

package chap2;

//2.3
//Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
//EXAMPLE
//Input: the node c from the linked list a->b->c->d->e
//Result: nothing isreturned, but the new linked list looks like a- >b- >d->e

/**
 * Ask the interviewer if this means that the middlenode won't be the first or
 * the last. If it is the first it doesn't matter. However if it is the last it
 * can't be deleted or you could set it to be a dummy node depending on the
 * interviewer. I assume the node that is to be deleted is not the last.
 * 
 * @author xl16
 * 
 */
public class DeleteFromList {

	/**
	 * Copy the value of each following node back one step, and put null after
	 * the 2nd to last node.
	 * 
	 * Time: O(n)
	 * 
	 * Space: O(1)
	 * 
	 * @param n
	 */
	public static void deleteNode(Node n) {
		// The node is a middle node, not the last, we can't delete the last in
		// this setting
		if (n == null || n.next == null) {
			return;
		}
		Node p1 = n;
		Node p2 = n.next;

		while (p2.next != null) {
			p1.data = p2.data;
			p1 = p1.next;
			p2 = p2.next;
		}
		p1.data = p2.data;
		p1.next = null;
	}

	/**
	 * Solution from the book, so simple... Copy the data from the next node
	 * over to the current node, and then delete the next node
	 * 
	 * Time: O(1)
	 * 
	 * Space: O(1)
	 * 
	 * @param n
	 */
	public static void deleteNodeEasy(Node n) {
		if (n == null || n.next == null) {
			return;
		}
		n.data = n.next.data;
		n.next = n.next.next;
		// //Or this chunk of code, it is the same
		// Node nextNode = n.next;
		// n.data = nextNode.data;
		// n.next = nextNode.next;
	}

	public static void main(String args[]) {
		DeleteFromList.Node head = new Node(0);
		head.appendToTail(1);
		head.appendToTail(2);
		head.appendToTail(3);

		System.out.println("Original                  : " + head.toString());
		// Get a middle node for the function to use
		Node middleNode = head.getNodeAt(2);
		System.out.println("To Delete                 : "
				+ middleNode.toString());
		// Do the deletion
		deleteNode(middleNode);
		System.out.println("After                     : " + head.toString());

	}

	/**
	 * Implementation of a simple LinkedList
	 * 
	 * @author xl16
	 * 
	 */
	static class Node {
		Node next = null;
		int data;

		public Node(int d) {
			data = d;
		}

		public int length() {
			int len = 0;
			Node n = this;
			while (n != null) {
				len += 1;
				n = n.next;
			}
			return len;
		}

		public Node getNodeAt(int k) {
			Node n = this;
			if (k > n.length() - 1) {
				System.err.println("Can't get Node at " + k
						+ ": it is larger than len-1");
				return null;
			}

			while (k > 0) {
				n = n.next;
				k--;
			}
			return n;
		}

		public void appendToTail(int d) {
			Node end = new Node(d);
			Node n = this;
			while (n.next != null) {
				n = n.next;
			}
			n.next = end;
		}

		public String toString() {
			Node n = this;
			String str = "";
			while (n.next != null) {
				str += String.valueOf(n.data) + "->";
				n = n.next;
			}
			// The last node
			str += String.valueOf(n.data) + "->null";
			return str;
		}
	}
}