-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0138 [M] Copy List with Random Pointer
Code with Senpai edited this page Sep 21, 2022
·
12 revisions
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]
footer