卖萌的弱渣

I am stupid, I am hungry.

Copy List With Random Pointer

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.

Challenge

Could you solve it with O(1) space?

Solution

  • Time: O(n), Space O(n)
  • For each old node, use hash_map(old_node, new_node) to test if old_node.next and old_node.random exists in the new list.
(Copy-List-With-Random-Pointer.py) download
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
42

# 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):
        # write your code here
        # Deep copy: coppy the whole list and connect all node together
        if head == None:
            return head
        # hash_map: {node_in_old_list, node_in_new_lsit}
        hash_map = {}
        dummy = RandomListNode(0)
        cur = dummy

        while head != None:
            # check if head in the hash_map
            if hash_map.has_key(head):
                new_node = hash_map[head]
            else:
                # create new one
                new_node = RandomListNode(head.label)
                hash_map[head] = new_node

            # new_node.next will be connected by the following line.
            cur.next = new_node

            # need to fix the new_node.random
            if head.random != None:
                if hash_map.has_key(head.random):
                    new_node.random = hash_map[head.random]
                else:
                    new_random_node = RandomListNode(head.random.label)
                    new_node.random = new_random_node
                    hash_map[head.random] = new_random_node
            cur = cur.next
            head = head.next
        return dummy.next
  • For the Space O(1) solution, you should firstly create all nodes and new_nodes.random = old_nodes.random. After that, you update the new_nodes.random