Copy List with Random Pointer

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Each node of a linked list has a value, a next pointer and a random pointer that can point at any node in the list or be null. Return a deep copy: brand-new nodes with the same values, whose next and random pointers mirror the original structure. No pointer in the copy may point into the original list, and the original must be unchanged when you return.

    The question is really about mapping: when you copy a node, how do you find the copy of the node its random points to? It is also a common warm-up for "clone a graph" questions. Original problem: LeetCode 138.

    Example

    Besides next, 13 points to 7, 11 to 10 and 10 back to 13; 7's random pointer is null.
    Besides next, 13 points to 7, 11 to 10 and 10 back to 13; 7's random pointer is null.
    Input (value, index of random):  [(7, null), (13, 0), (11, 3), (10, 1)]
    Output: a new list with the same pairs, made of 4 new nodes

    Constraints (assumed)

    • 0 ≤ n ≤ 1,000 nodes; values fit in a 32-bit integer.

    What this question tests

    • Building an old node → new node mapping, explicitly (hash map) or implicitly (interleaving).
    • Careful pointer manipulation, including restoring the original list.
    • Talking about the space trade-off between the two approaches.

    Questions to ask first

    1. Can random point to the node itself or be null? (Yes to both.)
    2. May I modify the original list temporarily? (Here: yes, as long as it is restored.)
    3. Is O(n) extra space acceptable? If yes, the hash map version is simplest.
    4. Can values repeat? (Yes, so you can't map by value.)