Leetcode 138. Copy List with Random Pointer

Problem

Leetcode 138 - Copy List with Random Pointer

Example:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Approach

We can solve this problem by using a HashMap.

In first iteration we loop through linked list to create a copy and add copy and curr into the map

In second iteration we loop through linked list to get a copy from the map, then link the next and random

Visualization of the Approach:

head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
map = {None: None} we have to put None as our random could be null

First iteration:
curr = [7, null]
copy = [7]
map = {None: None, [7, null]: [7]}

curr = [13, 0]
copy = [13]
map = {None: None, [7, null]: [7], [13,0] : [13]}

curr = [11, 4]
copy = [11]
map = {None: None, [7, null]: [7], [13,0] : [13], [11,4]:[11]}

curr = [10,2]
copy = [10]
map = {None: None, [7, null]: [7], [13,0] : [13], [11,4]:[11], [10,2] : [10]}

curr = [1, 0]
copy = [1]
map = {None: None, [7, null]: [7], [13,0] : [13], [11,4]:[11], [10,2] : [10], [1,0]: [1]}

Second iteration: start linking next and random
curr = [7, null]
copy = [7]
copy.next = 13
copy.random = null

curr = [13, 0]
copy = [13]
copy.next = 11
copy.random = 0

curr = [11,4]
copy = [11]
copy.next = 10
copy.random = 4

curr = [10,2]
copy = [10]
copy.next = 1
copy.random = 2

curr = [1,0]
copy = [1]
copy.next = null
copy.random = 0

Return oldNode[head] 

Here is the Python code for the solution:

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        oldNode = {None: None}

        curr = head
        while curr:
            copy = Node(curr.val)
            oldNode[curr] = copy
            curr = curr.next

        curr = head
        while curr:
            copy = oldNode[curr]
            copy.next = oldNode[curr.next]
            copy.random = oldNode[curr.random]
            curr = curr.next
    
        return oldNode[head]    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$