CopyListwithRandomPointer.java

/**
 * A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
 * Return a deep copy of the list.
 */

public class CopyListwithRandomPointer {
	public RandomListNode copyRandomList(RandomListNode head) {
		if (head == null)
			return head;
		RandomListNode cur = head;
		while (cur != null) {
			RandomListNode newNode = new RandomListNode(cur.label);
			newNode.next = cur.next;
			cur.next = newNode;
			cur = newNode.next;
		}
		cur = head;
		while (cur != null) {
			if (cur.random != null) {
				cur.next.random = cur.random.next;
			}
			cur = cur.next.next;
		}
		cur = head.next;
		RandomListNode newHead = cur;
		RandomListNode old = head;
		while (old != null) {
			old.next = old.next.next;
			if (old.next != null) {
				cur.next = old.next.next;
			}
			cur = cur.next;
			old = old.next;
		}
		return newHead;
	}
}