Katkat
Back

Deep copy a linked list with random pointers

MetaMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate complex pointer structures and maintain object identity across a deep copy operation in a non-linear linked list.

Problem Statement

You are given a linked list where each node contains an additional random pointer that 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 pointers of the new nodes must point to the new nodes in the copied list corresponding to the nodes in the original list. You must return the head of the copied list.

Node Structure

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

Example

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

  • The input is represented as a list of [value, random_index], where random_index is the index of the node the random pointer points to (or null).
  • Output: A new head of the list with identical structure and values, but independent object references.

Constraints

  • 0 <= n <= 1000
  • -10000 <= Node.val <= 10000
  • The random pointer is either null or points to a node in the list.

Edge Cases

  • Empty list (head = None).
  • A list with a single node.
  • Random pointer pointing to the node itself.

Hints

Hint 1

Consider using a hash map to store the mapping between the original nodes and their newly created copies.

Hint 2

Alternatively, try interleaving the copied nodes into the original list, where each original node is followed by its copy (A -> A' -> B -> B').

Hint 3

Once the list is interleaved, you can easily set the random pointers for the copies and then decouple the two lists.

Follow-up questions

  • What is the time and space complexity of your solution, and can you optimize the space complexity to O(1)?
  • How would your approach change if the graph were not a linked list, but a general directed graph with cycles?
  • If this linked list were distributed across multiple machines, how would you handle the serialization and mapping of random pointers?