The Problem:

In this problem, we are given a singly linked list with a random pointer at each node which can point to any other nodes in the linked list. Our goal is to return a deep copy of the list. A deep copy simply refers to another variable that is its own linked list & it does not reference the original variable.

Before we begin trying to figure out a solution for this problem, let’s first revisit an important concepts Linked List and Recursion.

Understanding Recursion:

Recursion is essentially a function calling itself. It is frequently used to solve problems that can be divided into smaller, similar sub-problems and can be very useful in dynamic programming. To understand recursion, it can be helpful to break it down into 3 parts:

1. Base Condition: This condition prevents the recursive function from calling itself infinitely.
2. Recursive Call: This is responsible for calling the recursive function itself.
3. Small Calculation: This step, which can come before or after the Recursive Call, is responsible for performing some calculation that we need for the recursive function or for returning some result after a recursive call has been completed.

A recursive tree is a visual representation of the recursive calls made by a function. It can be very helpful in understanding how recursion works and in analyzing the time and space complexity of recursive algorithms.

Understanding Linked List:

A linked list is a linear data structure that consists of a sequence of nodes, each containing data and a reference to the next node in the list. It is often used as an alternative to arrays, as it can be more efficient in certain operations such as insertion and deletion.

To understand linked lists, it can be helpful to break it down into 3 parts:

1. Nodes: Each node in a linked list contains some data and a reference to the next node in the list.
2. Head: The head of a linked list is the first node in the list. It is used as the starting point for many operations on the list.
3. Traversal: Traversing a linked list involves starting at the head and following the references from one node to the next until the desired node is reached or the end of the list is reached.

Linked lists can be very useful in solving problems that involve dynamic data structures, as they allow for efficient insertion and deletion of elements. They can also be used in combination with other data structures, such as stacks and queues, to solve more complex problems.

Intuition & Algorithm:

With an understanding of how recursion and linked lists work, let’s try to break down the problem. We don’t need to create our own linked list data structure because it is already provided. This is a fairly straightforward problem, so we will begin by figuring out the base condition, which in this case would be when the recursion reaches the end of the linked list (head == None). As for the actual recursive calculation, we can make use of the dictionary approach where we store each node in a hash map as key and the value being the copy, i.e. a new list node with the same value as the current node.

We can update this hash map as we call the function recursively for the next node of the copied node and when we hit the base condition, we check the hash map to find the random pointed node. we could then set the copied node's random pointer by using currentHead.random key in the hash map and set it's value.

Finally, we return the first copied node, which is the new head of the of the newly copied linked list.

Summary of Solution

Use recursion and a hash map to create a deep copy of a singly linked list with random pointers. At each recursive step, create a new node with the same value as the current node and store it in the hash map. Make recursive calls to copy the next and random nodes, and set the next and random pointers of the copied node accordingly. Return the first copied node as the new head of the copied list.

Code

This can be translated to code in the following way:

"""
# 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]':
        def helper(head, result = None, hashMap = {None: None}):
            if head == None: return head # BASE CASE
            copy = Node(head.val) # RECURSIVE CALCULATION
            hashMap[head] = copy
            copy.next = helper(head.next, copy, hashMap) # RECURSIVE CALL
            if head in hashMap: # RECURSIVE CALCULATION
                copy.random = hashMap[head.random]
            return copy
        return helper(head)

• Time Complexity O(n)
• Space Complexity O(n)

The time complexity of this solution is O(n) This is because the function needs to traverse the linked lists to clone it. Time taken for this operation would be proportional to the size of the linked list.

Space complexity is O(n) because of recursion call stack.

This approach is simple and efficient, making it a good solution to this problem.

I hope you enjoyed this post. Stay tuned for daily LeetCode blog posts!