Description

cr: https://leetcode-cn.com/problems/copy-list-with-random-pointer

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random –> Y, then for the corresponding two nodes x and y in the copied list, x.random –> y.

Return the head of the copied linked 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) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Constraints:

  • 0 <= n <= 1000
  • -104 <= Node.val <= 104
  • Node.random is null or is pointing to some node in the linked list.

Solution

Understanding what this question really want you to do is really significant. I read this question in Chinese and was confused by the question. According to examples’ inputs and outputs I wrote 

1
2
3
class Solution(object):
    def copyRandomList(self, head):
        return self.head

as solution. That was wrong. This question asked me to deep-copy this list.

Method1

To acheive this we can just call copy.deepcopy(head_node). This solution is short but not funny.

Method2

  1. Make a dictionary to store old nodes ~ new nodes as keys and values.
  2. Copy old nodes’ values to new nodes. However, new nodes’ randoms all point to old nodes.
  3. Iterate new nodes and change their random pointers to point to the new nodes.

What is deep-copy?

Deep copying an object is to make a new object with same attributes as the old one. The only difference between the new and old objects is their address.

Source Code

Method 1

1
2
3
class Solution(object):
    def copyRandomList(self, head):
        return copy.deepcopy(head)

Method 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
"""
# Definition for a Node.
class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if head:
            # copy values to new nodes
            cur = head.next
            new_head = Node(head.val, head.next)
            dic = {}
            if head.random:
                new_head.random = head.random
            dic[head] = new_head
            prev = new_head
            while cur:
                new_cur = Node(cur.val, cur.next)
                prev.next = new_cur
                if cur.random:
                    new_cur.random = cur.random
                dic[cur] = new_cur
                cur = cur.next
                prev = new_cur
            # add the random pointer
            n_cur = new_head.next
            if new_head.random:
                new_head.random = dic[new_head.random]
            while n_cur:
                if n_cur.random:
                    n_cur.random = dic[n_cur.random]
                n_cur = n_cur.next
            return new_head
        return None