Clone list with random pointers
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
You are given the head of a singly linked list where each node has two pointers: next and random (which may be null or point to any node). Construct a deep copy of the list and return the head of the copy. Aim for O(n) time. Explain both a hash-map approach and an in-place weaving approach that achieves O(
1) auxiliary space. Discuss handling cycles in random pointers and how you verify structural equality.
Quick Answer: This question evaluates a candidate's ability to manipulate complex linked data structures and reason about deep-copy semantics, pointer integrity, time-space trade-offs, and edge cases such as cycles in auxiliary (random) pointers.