Katkat
Back

Copy a Linked List with Random Pointers

AppleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manipulate linked structures and manage pointer state without using extra hash maps for space optimization.

Problem Statement

A linked list 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 pointers of the new nodes must point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. You must return the head of the copied linked list.

Constraints

  • The number of nodes in the list is in the range [0, 1000].
  • -10000 <= Node.val <= 10000
  • Node.random is null or points to a node in the list.
  • Requirement: You must achieve this using O(1) auxiliary space (excluding the space required for the new nodes).

Function Signature

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

def copyRandomList(head: 'Node') -> 'Node':
    pass

Example

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] (Format: [value, index_of_random_pointer_or_null])

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

Explanation: The list is copied such that the pointer structure is identical. The new nodes are separate memory objects from the original nodes.

Hints

Hint 1

Consider interleaving the new nodes directly into the original list (A -> A' -> B -> B' -> C -> C').

Hint 2

Once the list is interleaved, you can easily map the random pointers of the original nodes to the new nodes by setting new_node.random = old_node.random.next.

Hint 3

Finally, separate the interleaved list into two distinct lists to restore the original list and isolate the copy.

Follow-up questions

  • How would you handle the memory management if this were implemented in a language like C++ without a garbage collector?
  • Could you solve this problem if the random pointer could point to nodes outside the current linked list structure?
  • What are the trade-offs between the O(1) space approach and an O(n) space approach using a hash map?