Copy List with Random Pointer

Source

• lintcode: Copy List with Random Pointer

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.

Example
Challenge
Could you solve it with O(1) space?

Java

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;

        Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();

        // loop 1. copy all the nodes
        RandomListNode node = head;
        while (node != null) {
            map.put(node, new RandomListNode(node.label));
            node = node.next;
        }

        // loop 2. assign next and random pointers
        node = head;
        while (node != null) {
            map.get(node).next = map.get(node.next);
            map.get(node).random = map.get(node.random);
            node = node.next;
        }

        return map.get(head); 
    }
}

Java O(1)

public RandomListNode copyRandomList(RandomListNode head) {  
    if(head == null)  
        return head;  
    RandomListNode node = head;  

    while(node!=null){  
        RandomListNode newNode = new RandomListNode(node.label);  
        newNode.next = node.next;  
        node.next = newNode;  
        node = newNode.next;  
    }  

    node = head;  
    while(node!=null){  
        if(node.random != null)  
            node.next.random = node.random.next;  
        node = node.next.next;  
    }  

    RandomListNode newHead = head.next;  
    node = head;  
    while(node != null){  
        RandomListNode newNode = node.next;  
        node.next = newNode.next;  
        if(newNode.next!=null)  
            newNode.next = newNode.next.next;  
        node = node.next;  
    }  
    return newHead;  
}

Python

# Definition for singly-linked list with a random pointer.
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # @param head: A RandomListNode
    # @return: A RandomListNode
    def copyRandomList(self, head):
        if head is None:
            return None
        map = {}

        node = head
        while node:
            map[node] = RandomListNode(node.label)
            node=node.next

        node = head
        while node:
            if node.next:
                map[node].next = map[node.next]
            else:
                map[node].next = None

            if node.random:
                map[node].random = map[node.random]
            else:
                map[node].random = None

            node=node.next

        return map[head]

Reference

Copy List with Random Pointer