cloning the ll into another using deep copy
- initially we use hashmap to implement it .
"""
# 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 None
h = {}
curr = head
while curr != None:
h[curr] = Node(curr.val)
curr = curr.next
curr = head
while curr != None:
copy = h[curr] # this is where we are copying inside the dictionary itself.
copy.next = h.get(curr.next)
copy.random = h.get(curr.random)
curr = curr.next
curr = head
return h[curr]
Time complexity :
O(n)
space complexity
O(n) # which is bad
optimization
- we need to reduce space complexity alone.
"""
# 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 None
# h = {}
# curr = head
# while curr != None:
# h[curr] = Node(curr.val)
# curr = curr.next
# curr = head
# while curr != None:
# copy = h[curr]
# copy.next = h.get(curr.next)
# copy.random = h.get(curr.random)
# curr = curr.next
# curr = head
# return h[curr]
# optimal solutions
if not head:
return None
curr = head
while curr!= None:
copy = Node(curr.val)
copy.next = curr.next
curr.next = copy
curr = curr.next.next
# now the array will look like this " a-a'-b-b'-c-c'"
curr = head
while curr != None:
if curr.random :
curr.next.random = curr.random.next
curr= curr.next.next
# now it will point the random too since curr.next.random is for copied part and curr.random.next is for copied partof random.
# now we need to separate
curr = head
curr_head = curr.next
while curr:
copy = curr.next
curr.next = copy.next
if copy.next:
copy.next = copy.next.next
curr = curr.next
return curr_head
- now it has O(1) space complexity
Interview Explanation:
Initially we plan using hashmap which will use lookup of O(1) but we need space complexity of O(1) , to overcome it , we are use the same array , by inserting the copied inside the real linked list. and at last splitting that into two linkedlist.