Make a deep copy of a linked list


  • 1
    A

    Each node of the original linked list will have next pointers as well as random pointers that can point to any element in the list or to a null. The deep copy must make an entirely new linked list with no pointers to the original list.


  • 0
    C
    This post is deleted!

  • -1

    The idea below is to map between the node in the new list and the old list, you can this map later to reconstruct the random node

    public void problemDeepArrayListCopy(Node head) {
    		Deque<Node> stack = new LinkedList<>();
    		Map<Node, Node> map = new HashMap<>();
    		Node tmp = head;
    		
    		while(tmp != null) {
    			stack.push(tmp);
    			tmp = tmp.next;
    		}
    		// reverse original list
    		Node head2 = null, end = null;
    		while(!stack.isEmpty()) {
    			Node popped = stack.pop();
    			tmp = new Node(popped.data);
    			// map between node in new list and node in old list
    			map.put(tmp, popped);
    			if(head2 == null)
    				head2 = end = tmp;
    			else {
    				end.next = tmp;
    				end = tmp;
    			}
    		}
    		
    		tmp = head2;
    		// copy the random
    		while(tmp != null) {
    			Node oldRandom = map.get(tmp).random;
    			Node newRandom = head2;
    			while(newRandom != null && map.get(newRandom) != oldRandom)
    				newRandom = newRandom.next;
    			if(newRandom != null)
    				tmp.random = newRandom;
    			tmp = tmp.next;
    		}
    		// return head2;
    	}
    

Log in to reply
 

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