CC_2_3

CurrentNodeRemoval.java

// Cracking the Coding Interview
// 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

class Node {
	public Node next;
	public int val;
	Node(int _v) {
		val = _v;
		next = null;
	}
}

class CurrentNodeRemoval {
	// if n is the last node in the linked list, do nothing
	public static void removeCurrentNode(Node n) {
		if (n == null || n.next == null) return;
		n.val = n.next.val;
		n.next = n.next.next;
		return;
	}
	public static void main(String[] args) {
		Node test1 = arrayToLinkedList(new int[]{1, 2, 3});
		Node test2 = arrayToLinkedList(new int[]{1, 2, 3});
		Node test3 = arrayToLinkedList(new int[]{1});
		Node test4 = arrayToLinkedList(new int[]{1, 2, 3, 4});

		removeCurrentNode(test1);
		removeCurrentNode(test2.next);
		removeCurrentNode(test3);
		removeCurrentNode(test4.next.next);

		assert compareLinkedList(test1, arrayToLinkedList(new int[]{2, 3}));
		assert compareLinkedList(test2, arrayToLinkedList(new int[]{1, 3}));
		assert compareLinkedList(test3, arrayToLinkedList(new int[]{1}));
		assert compareLinkedList(test4, arrayToLinkedList(new int[]{1, 2, 4}));

		System.out.println("Test Passed");
	}

	private static boolean compareLinkedList(Node a, Node b) {
		Node p1 = a;
		Node p2 = b;
		while (p1 != null && p2 != null) {
			if (p1.val != p2.val) {
				return false;
			} else {
				p1 = p1.next;
				p2 = p2.next;
			}
		}

		return p1 == null && p2 == null;
	}

	private static Node arrayToLinkedList(int[] arr) {
		if (arr == null || arr.length < 1) return null;
		Node fakeHead = new Node(0);
		Node cur = fakeHead;
		for(int i = 0; i < arr.length; i++) {
			cur.next = new Node(arr[i]);
			cur = cur.next;
		}
		return fakeHead.next;
	}
}

1. Good job!