Copy List with Random Pointer @LeetCode

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.

	package leetcode;
	import java.util.Random;
	/**
	* Problem: 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.
	*
	* Solution:
	* We can't copy them from head to rear because there's no node when we copy random pointer.
	* 1. We can copy the a node after original node. there're double nodes after copyNext.
	* 2. Then copy random. head.next.random = head.random.next. Take care of situation random = null. need to judge.
	* 3. Split the list into two same list.
	*
	* My Thought.
	* 1. head.next.random != null. --> no need. but as they may be null, null pointer problem exist. (I didn't understand problem)
	* 2. newNode.random = head.random --> no need. We need to findout if the node's random is null.
	* Codes needs to be changed like this. if (head.random != null) in copyRandom. works but not straightforward like following.
	*
	*
	* TestCase:
	* Random Pointer could be null
	*
	*
	* @author jeffwan
	* @date Feb 27, 2014
	*/
	public class CopyRandomList {
	public RandomListNode copyRandomList(RandomListNode head) {
	if (head == null) {
	return null;
	}
	copyNext(head);
	copyRandom(head);
	return splitList(head);
	}
	public void copyNext(RandomListNode head) {
	while (head != null) {
	RandomListNode newNode = new RandomListNode(head.label);
	newNode.next = head.next;
	newNode.random = head.random;
	head.next = newNode;
	head = head.next.next;
	}
	}
	public void copyRandom(RandomListNode head) {
	while (head != null) {
	if (head.next.random != null) {
	head.next.random = head.random.next;
	}
	head = head.next.next;
	}
	}
	public RandomListNode splitList(RandomListNode head) {
	RandomListNode newHead = head.next;
	while (head != null) {
	RandomListNode temp = head.next;
	head.next = temp.next;
	head = head.next;
	if (temp.next != null) {
	temp.next = temp.next.next;
	}
	}
	return newHead;
	}
	}
	class RandomListNode {
	int label;
	RandomListNode next, random;
	RandomListNode(int x) {this.label = x; }
	}

view raw CopyRandomList.java hosted with ❤ by GitHub