LC 0138 [M] Copy List with Random Pointer - ALawliet/algorithms GitHub Wiki

T: O(n), S: O(1)

"""
# 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: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return head

        # 1) make a ' copy next to each original
        c = head
        while c:
            oldnext = c.next # temp (2)
            c.next = Node(c.val) # (1->1`)
            c.next.next = oldnext # (1->1`->2)
            c = oldnext # (2)
        
        # 2) assign the random pointers for the clones using the originals
        c = head
        while c: # all nodes
            if c.random: # original has random
                c.next.random = c.random.next # clone's random = current random's clone
            c = c.next.next
            
        # 3) split off the copy
        cloneHead = head.next
        _c = cloneHead # clone pointer
        while _c.next: # we're starting at the 2nd and want to go 1 past the last to the last clone so check .next
            _c.next = _c.next.next # skip over the next current to the next clone
            _c = _c.next
        
        return copyHead

T: O(n), S: O(n)

"""
# 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:
    # @param head, a RandomListNode
    # @return a RandomListNode
    def copyRandomList(self, head):
        d = defaultdict(lambda: Node(0))
        d[None] = None
        c = head
        while c:
            d[c].val = c.val
            d[c].next = d[c.next]
            d[c].random = d[c.random]
            c = c.next
        return d[head]