LeetCode: 138. Copy List with Random Pointer

O(N) Time, O(N) Memory

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return
        cur, dic = head, {}
        while cur:
            dic[cur] = Node(x=cur.val)
            cur = cur.next
        cur = head
        while cur:
            if cur.next:
                dic[cur].next = dic[cur.next]
            if cur.random:
                dic[cur].random = dic[cur.random]
            cur = cur.next
        return dic[head]

 

O(N) Time, O(1) Memory

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return
        cur = head
        while cur:
            nxt = cur.next
            new_node = Node(x=cur.val)
            cur.next = new_node
            new_node.next = nxt
            cur = nxt                        
        cur = head
        while cur:
            if cur.random:
                 cur.next.random = cur.random.next
            cur = cur.next.next
        cur = head.next
        while cur.next:
            nxt = cur.next.next
            cur.next = nxt
            cur = nxt
        return head.next