leetcode/Python/138_Copy_List_With_Random_Pointer.py at main · CPWu/leetcode · GitHub

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
"""
# 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):
#     # Time: O(N), Space: O(N)
#     def copyRandomList(self, head):
#         """
#         :type head: Node
#         :rtype: Node
#         """
#         if not head:
#             return head

#         old_node = new_node = Node(-1, None, None)
#         current_node = head
#         old_new = {}

#         # Generate a new list / hash old -> new
#         while current_node:
#             new_node.next = Node(current_node.val)
#             old_new[current_node] = new_node.next
#             current_node = current_node.next
#             new_node = new_node.next
#         current_node = head
#         new_node = old_node.next

#         # Update new list with new nodes for random
#         while current_node:
#             if current_node.random:
#                 new_node.random = old_new[current_node.random]
#             current_node = current_node.next
#             new_node = new_node.next
#         return old_node.next

    # Time: O(N), Space: O(1)
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return head

        # Creating a new weaved list of original and copied nodes.
        pointer = head
        while pointer:
            # Cloned Node
            new_node = Node(pointer.val, None, None)

            new_node.next = pointer.next
            pointer.next = new_node
            pointer = new_node.next

        pointer = head

        while pointer:
            pointer.next.random = pointer.random.next if pointer.random else None
            pointer = pointer.next.next

        pointer_old_list = head
        pointer_new_list = head.next
        head_new = head.next
        while pointer_old_list:
            pointer_old_list.next = pointer_old_list.next.next
            pointer_new_list.next = pointer_new_list.next.next if pointer_new_list.next else None
            pointer_old_list = pointer_old_list.next
            pointer_new_list = pointer_new_list.next
        return head_new