Question

Formatted question description: https://leetcode.ca/all/138.html

138	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.

The Linked List is represented in the input/output as a list of n nodes.
Each node is represented as a pair of [val, random_index] where:
    * val: an integer representing Node.val
    * random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Constraints:
    -10000 <= Node.val <= 10000
    Node.random is null or pointing to a node in the linked list.
    Number of Nodes will not exceed 1000.

@tag-linkedlist

Algorithm

Three steps, with no extra space:

  1. Copy a new node behind each node in the original linked list.

  2. Assign values ​​to the random pointers of new nodes in turn, and this assignment is very easy cur->next->random = cur->random->next.

  3. Disconnect the linked list to get a new linked list after deep copy.

For example, for example, the original linked list is 1(2) -> 2(3) -> 3(1), and the node pointed to by its random pointer is in parentheses, so this solution is to first traverse the original linked list. Copy a same node after each node, but the random pointer of the copied node is still empty, then the original linked list becomes 1(2) -> 1(null) -> 2(3) -> 2(null ) -> 3(1) -> 3(null). Then the second traversal is to assign the correct value to the random pointer of the copy node, and the original linked list becomes 1(2) -> 1(2) -> 2(3) -> 2(3) -> 3 (1) -> 3(1), note that the assignment statement is:

cur->next->random = cur->random->next;

Here cur is the node in the original linked list, cur->next is the node of the copied linked list, and cur->next->random is the random pointer of the copied linked list. cur->random is the node pointed to by the random pointer of the original linked list node. Because it points to the node of the original linked list, we have to add another next to point to the node of the copied linked list. The last traversal is to disconnect the original linked list from the copy linked list.

Code

Java

  • public class Copy_List_with_Random_Pointer {
    
        /**
         * Definition for singly-linked list with a random pointer.
         * class RandomListNode {
         *     int label;
         *     RandomListNode next, random;
         *     RandomListNode(int x) { this.label = x; }
         * };
         */
    
        /*
            1. 在原链表的每个节点后面拷贝出一个新的节点。
            2. 依次给新的节点的随机指针赋值,而且这个赋值非常容易 cur->next->random = cur->random->next。
            3. 断开链表可得到深度拷贝后的新链表。
         */
        public class Solution_noExtraMap {
            public RandomListNode copyRandomList(RandomListNode head) {
                if (head == null) {
                    return null;
                }
    
                // duplicate new node right after
                RandomListNode current = head;
                while (current != null) {
                    RandomListNode t = new RandomListNode(current.label);
                    t.next = current.next;
                    current.next = t;
                    current = t.next;
                }
    
                // random pointer update for duplicate new node
                current = head;
                while (current != null) {
                    if (current.random != null) {
                        current.next.random = current.random.next;
                    }
                    current = current.next.next;
                }
    
                // cut copied list out
                current = head;
                RandomListNode res = head.next;
                while (current != null) {
                    RandomListNode t = current.next;
                    current.next = t.next;
                    if (t.next != null) {
                        t.next = t.next.next;
                    }
                    current = current.next;
                }
    
                return res;
            }
        }
    
        public class Solution {
    
            // map from original node, to its copy node
            HashMap<RandomListNode, RandomListNode> hm = new HashMap<>();
    
            public RandomListNode copyRandomList(RandomListNode head) {
    
                if (head == null) {
                    return null;
                }
    
                RandomListNode current = head;
    
                while (current != null) {
    
                    RandomListNode currentCopy = getNodeCopy(current);
    
                    RandomListNode currentNextCopy = getNodeCopy(current.next);
                    RandomListNode currentRandomCopy = getNodeCopy(current.random);
    
                    currentCopy.next = currentNextCopy;
                    currentCopy.random = currentRandomCopy;
    
                    current = current.next;
                }
    
                return hm.get(head);
            }
    
            private RandomListNode getNodeCopy (RandomListNode originalNode) {
    
                if (originalNode == null) { // @note: missed this check, last node will cause error, whose next is null
                    return null;
                }
    
                if (hm.containsKey(originalNode)) {
                    return hm.get(originalNode);
    
                } else {
                    RandomListNode nodeCopy = new RandomListNode(originalNode.label);
                    hm.put(originalNode, nodeCopy);
    
                    return nodeCopy;
                }
            }
        }
    
    }
    
  • // OJ: https://leetcode.com/problems/copy-list-with-random-pointer/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        Node* copyRandomList(Node* head) {
            auto p = head;
            while (p) {
                auto node = p;
                p = p->next;
                auto copy = new Node(node->val);
                node->next = copy;
                copy->next = p;
            }
            p = head;
            while (p) {
                if (p->random) p->next->random = p->random->next;
                p = p->next->next;
            }
            p = head;
            Node h(0), *tail = &h;
            while (p) {
                auto node = p->next;
                p->next = node->next;
                p = p->next;
                tail->next = node;
                tail = node;
            }
            return h.next;
        }
    };
    
  • # Definition for singly-linked list with a random pointer.
    # class RandomListNode(object):
    #     def __init__(self, x):
    #         self.label = x
    #         self.next = None
    #         self.random = None
    
    class Solution(object):
      def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        p = head
        while p:
          copy = RandomListNode(p.label)
          copy.next = p.next
          p.next = copy
          p = copy.next
    
        p = head
        while p:
          p.next.random = p.random and p.random.next
          p = p.next.next
    
        p = head
        copy = chead = head and head.next
        while p:
          p.next = p = copy.next
          copy.next = copy = p and p.next
        return chead
    
    

All Problems

All Solutions