Introduction

In this blog post, we will explore how to solve the LeetCode problem "138" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null. Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list. For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y. Return the head of the copied linked list. The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where: val: an integer representing Node.val random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node. Your code will only be given the head of the original linked list. Example 1: Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]] Example 2: Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]] Example 3: Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]] Constraints: 0 <= n <= 1000 -104 <= Node.val <= 104 Node.random is null or is pointing to some node in the linked list.

Explanation

Here's a solution to the deep copy of a linked list with random pointers problem.

• High-Level Approach:

  • Iterate through the original list and create a copy of each node. Store the mapping between original and copied nodes in a dictionary.
  • Iterate through the original list again. For each node, use the dictionary to find the corresponding copied node and set its next and random pointers to the copied versions of the original node's next and random nodes.

• Complexity:

  • Runtime: O(n), where n is the number of nodes in the linked list. Storage: O(n) for the dictionary.

Code

    class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

def deepCopyRandomList(head: 'Node') -> 'Node':
    """
    Given a linked list, create a deep copy of it with random pointers.
    """
    if not head:
        return None

    # Dictionary to store the mapping between original and copied nodes.
    node_map = {}

    # First pass: Create copies of all nodes and store them in the dictionary.
    curr = head
    while curr:
        node_map[curr] = Node(curr.val)
        curr = curr.next

    # Second pass: Set the next and random pointers of the copied nodes.
    curr = head
    while curr:
        copied_node = node_map[curr]
        copied_node.next = node_map.get(curr.next)  # Use .get() to handle None
        copied_node.random = node_map.get(curr.random)  # Use .get() to handle None
        curr = curr.next

    return node_map[head]