Linkedlist leetcode

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.