Only 10 lines easy Java code with recursion:)


  • 0

    Here's my code, I came out with an idea with recursion to clearly handle RandomListNode.next and RandomListNode.random
    The key thing of this question is to get away with an infinitely running time because of the random node, which can point to another node that had called recursion before and over and over again.
    I used a HashMap to store every node that we have met in the recursion. If we run into the node that is just in the HashMap, we will get away from recursion and jump back with the value HashMap.get(node) :)

     public class DeepCopy {
     public static Map<RandomListNode, RandomListNode> nodeMap = new HashMap<RandomListNode, RandomListNode>();
     public RandomListNode copyRandomList(RandomListNode head) {
    	RandomListNode result = null;
    	if (head == null)
    		return result;
    	if (nodeMap.containsKey(head))
    		return nodeMap.get(head);
    	result = new RandomListNode(head.label);
    	nodeMap.put(head, result);
    	result.next = copyRandomList(head.next);
    	result.random = copyRandomList(head.random);
    	return result;
    }}

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.