Start learning free

LESSON 309 OF 415 · LINKED LISTS

Copy List with Random Pointer in Swift: O(n) with a Dictionary

Practice O(n) Read the full explanation

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 nil.

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, the value of the node
  • random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or nil 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]]

Example 4:

Input: head = []
Output: []
Explanation: The given linked list is empty (nil), so return nil.

 

Constraints:

  • 0 <= n <= 1000
  • -10000 <= val <= 10000
  • random is nil or is pointing to some node in the linked list.

Note:

Your algorithm should run in O(n) time and use at most O(n) extra space.


STEP 1 OF 11
    Ctrl + Enter to check

    SWIFT · LINKED LISTS

    Copy List Random Pointer in Swift, explained

    Problem overview

    The method copyRandomList receives the head of a singly linked list in which every ListNode has a val, a next link and a random link. The random link points to any node of the same list, or is nil. The method must build a deep copy: exactly as many brand-new nodes as the original, with the same values, where the next and random links of the new nodes point to new nodes only. No link of the copy may lead back into the original list. It returns the head of the copy, or nil for an empty list.

    In the first example the nodes, written as [val, random_index], are [7,null], [13,0], [11,4], [10,2] and [1,0]. The copy has the same five values in the same order, and its random links point to the same positions: the second copied node points at the first copied node, the third at the fifth, and so on. The statement asks for O(n) time and allows O(n) extra space.

    Approach: a map from each original to its copy

    Copying the values and the next chain is easy. The hard part is the random link, which may point forward or backward, so when a copy is created its target may have no copy yet.

    The fix is to separate the work into two passes:

    1. Pass 1: walk the original list and create one new node for each original, holding only the value. Store each pair in a dictionary: original in, copy out.
    2. Pass 2: walk the original list again. Now every original has a copy, so for each node the dictionary gives the copy of the node, the copy of its successor, and the copy of its random target. Set the copy's next and random from those.

    The dictionary needs a key that identifies a node as an object. The value in val is not enough, since the third example has three different nodes that all hold 3. The key must be the identity of the node.

    Step by step

    1. Create the dictionary copies of type [ObjectIdentifier: ListNode]. A class instance isn't hashable by default, but ObjectIdentifier(obj) wraps its identity in a value that is. Two nodes holding the same value remain separate keys.
    2. Start a walker var node = head. The head itself stays untouched, since the second pass and the return value need it.
    3. Loop while node != nil. Inside, node is still an optional, and ! is safe because the condition just checked it.
    4. Store a new node for the original: copies[ObjectIdentifier(node!)] = ListNode(node!.val). Only the value is copied here. The links are wired later, when every copy exists.
    5. Advance with node = node!.next. Without it the loop never ends.
    6. Reset the walker to head for the second pass.
    7. Loop again while node != nil.
    8. Wire next. The copy of node is copies[ObjectIdentifier(node!)]!. Its next is the copy of the original's successor, or nil when there is no successor. A ternary chooses between the two, because ObjectIdentifier can't be built from a nil.
    9. Wire random the same way, using node!.random.
    10. Advance along the original list with node = node!.next.
    11. Return the copy of the head, or nil when head is nil. The check comes first, because ObjectIdentifier(head!) would crash on an empty list.

    The solution in Swift

    class Solution {
    func copyRandomList(_ head: ListNode?) -> ListNode? {
        var copies = [ObjectIdentifier: ListNode]()
        var node = head
        while node != nil {
            copies[ObjectIdentifier(node!)] = ListNode(node!.val)
            node = node!.next
        }
        node = head
        while node != nil {
            copies[ObjectIdentifier(node!)]!.next = node!.next == nil ? nil : copies[ObjectIdentifier(node!.next!)]
            copies[ObjectIdentifier(node!)]!.random = node!.random == nil ? nil : copies[ObjectIdentifier(node!.random!)]
            node = node!.next
        }
        return head == nil ? nil : copies[ObjectIdentifier(head!)]
    }
}

    Swift details worth knowing:

    • Why ObjectIdentifier. Declaring [ListNode: ListNode] doesn't compile for a plain class, because the class doesn't conform to Hashable. ObjectIdentifier is hashable and is equal exactly when two references point at the same object.
    • A dictionary subscript returns an optional. copies[key] has type ListNode?. The trailing ! in copies[ObjectIdentifier(node!)]! is safe, since the first pass stored a copy for every original. For the right-hand sides, the optional is exactly what the next and random properties accept.
    • Assigning through a force-unwrap. copies[...]!.next = ... changes the stored object. ListNode is a class, so the dictionary holds a reference, and writing through it updates the same object.
    • The ternary with nil. In cond ? nil : copies[...], both branches become ListNode?, which matches the property's type.
    • The lookup could be shorter. Optional chaining such as node!.next.flatMap { copies[ObjectIdentifier($0)] } avoids the explicit nil check, but the lesson's version is easier to read for a beginner.

    Complexity

    Time: O(n). Each pass visits every node once, and a dictionary lookup or insertion takes constant time on average.

    Space: O(n). The dictionary holds one entry per node, in addition to the n new nodes that the answer needs anyway. The follow-up version of this problem removes the dictionary by interleaving the copies with the originals.

    Edge cases and common mistakes

    • Empty list. The loops don't run and the last line returns nil. Writing copies[ObjectIdentifier(head!)] without the head == nil check would crash.
    • Equal values. [3,null], [3,0], [3,null] has three distinct nodes with the same value. Identity keys keep them separate. A value-based key would merge them.
    • Random pointing to itself. A node whose random is the node itself gets a copy whose random is the copy itself, because the lookup returns that node's own copy.
    • Random pointing forward. The second pass handles it, because every copy already exists. A single pass that wires links while copying would not have the target yet.
    • Linking to originals. Assigning node!.random directly to the copy would make the copy point into the original list, which the statement forbids.
    • Not resetting node. After the first loop, node is nil. Without node = head the second loop would not run, and no link would be wired.

    Testing

    • [7,null], [13,0], [11,4], [10,2], [1,0] gives a list with the same values and random positions, made of new nodes.
    • [1,1], [2,1] gives the same structure: both random links point at the second node.
    • [3,null], [3,0], [3,null] gives three separate new nodes; only the second has a random link, to the first.
    • An empty list gives nil.
    • A single node [5,0], whose random points to itself, gives one new node whose random is itself.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free