Solving Copy List with Random Pointer in Go: Step-by-Step Guide

Introduction to the Copy List with Random Pointer Problem

The "Copy List with Random Pointer" problem is a classic algorithmic challenge frequently encountered in coding interviews and computer science coursework. The task involves creating a deep copy of a linked list where each node contains not only a Next pointer (as in a standard singly linked list) but also a Random pointer that can point to any node in the list — or to nil. The challenge lies in correctly reconstructing these random connections in the new list without accidentally sharing references with the original.

While the problem sounds straightforward, the random pointers introduce a subtle complication: when you copy a node, its random target may not yet exist in the new list. This forces developers to think carefully about ordering, memory, and reference management. In Go, where pointers are explicit and memory safety is enforced by the runtime, this problem offers an excellent opportunity to practice pointer manipulation and map-based lookups.

Why This Problem Matters

Beyond its interview popularity, the Copy List with Random Pointer problem models real-world scenarios where data structures contain non-linear references. Examples include:

Graph-like data structures where nodes reference each other in arbitrary patterns.
Document object models with cross-references between elements.
Serialization and deserialization of complex object graphs.
Undo/redo systems that need snapshots of stateful structures.

Mastering this problem teaches two fundamental techniques: using hash maps to track node correspondences, and in-place pointer weaving to achieve constant extra space. Both techniques appear repeatedly in more advanced problems involving graphs, trees, and object cloning.

Understanding the Node Structure

Before diving into solutions, let's define the node structure in Go. Each node holds an integer value, a pointer to the next node, and a pointer to an arbitrary node within the list.

package main

// Node represents a node in the linked list with a random pointer.
type Node struct {
    Val    int
    Next   *Node
    Random *Node
}

The Val field stores the node's data, Next points to the subsequent node in sequence, and Random can point to any node in the list (including itself) or be nil. A typical input list might look like: 7 -> 13 -> 11 -> 10 -> 1, where node 13's random points to node 7, node 11's random points to node 1, and so on.

Approach 1: Hash Map Based Solution

The most intuitive approach uses a hash map to record the mapping between original nodes and their copies. The algorithm proceeds in two passes:

First pass: Iterate through the original list and create a copy of each node, storing the mapping original -> copy in a map.
Second pass: Iterate again and assign Next and Random pointers for each copy by looking up the corresponding copies in the map.

This approach runs in O(n) time and uses O(n) extra space for the map.

package main

// copyRandomList creates a deep copy of the list using a hash map.
func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }

    // Map each original node to its copy.
    nodeMap := make(map[*Node]*Node)

    // First pass: create copies of all nodes.
    current := head
    for current != nil {
        nodeMap[current] = &Node{Val: current.Val}
        current = current.Next
    }

    // Second pass: assign Next and Random pointers.
    current = head
    for current != nil {
        copyNode := nodeMap[current]
        copyNode.Next = nodeMap[current.Next]
        copyNode.Random = nodeMap[current.Random]
        current = current.Next
    }

    return nodeMap[head]
}

Notice how the map lookup handles nil gracefully: when current.Next or current.Random is nil, the map returns the zero value for a pointer, which is nil — exactly what we want.

Walking Through the Hash Map Approach

Consider a list with three nodes: A (val 1, random C), B (val 2, random A), C (val 3, random nil). After the first pass, the map contains three entries mapping A, B, and C to their fresh copies. During the second pass, when processing node A, we look up nodeMap[C] to set the copy's random pointer, ensuring the new node references the new copy of C — not the original. This guarantees a true deep copy.

Approach 2: In-Place Interweaving (O(1) Space)

For situations where memory is constrained, we can eliminate the hash map by weaving copied nodes directly into the original list. The strategy has three phases:

Phase 1: Insert a copy of each node immediately after the original node, creating an interleaved list: A -> A' -> B -> B' -> C -> C'.
Phase 2: Assign random pointers for the copies. Since each copy sits right after its original, the copy's random is simply original.Random.Next (if original.Random is not nil).
Phase 3: Detach the copied nodes to restore the original list and extract the new list.

package main

// copyRandomListConstantSpace creates a deep copy using O(1) extra space.
func copyRandomListConstantSpace(head *Node) *Node {
    if head == nil {
        return nil
    }

    // Phase 1: Interleave copied nodes with original nodes.
    current := head
    for current != nil {
        copyNode := &Node{Val: current.Val}
        copyNode.Next = current.Next
        current.Next = copyNode
        current = copyNode.Next
    }

    // Phase 2: Assign random pointers to the copied nodes.
    current = head
    for current != nil {
        if current.Random != nil {
            current.Next.Random = current.Random.Next
        }
        current = current.Next.Next
    }

    // Phase 3: Separate the two lists.
    current = head
    copyHead := head.Next
    for current != nil {
        copyNode := current.Next
        current.Next = copyNode.Next
        if copyNode.Next != nil {
            copyNode.Next = copyNode.Next.Next
        }
        current = current.Next
    }

    return copyHead
}

This approach achieves O(n) time with O(1) extra space (excluding the output list). The trade-off is that it temporarily mutates the original list, which may be undesirable if the original must remain untouched during the operation. Although the original list is restored by the end, concurrent readers could observe inconsistent state mid-operation.

Testing the Implementation

A robust solution deserves thorough testing. Below is a complete test harness that constructs a sample list, copies it, and verifies that the copy is structurally identical but physically distinct from the original.

package main

import (
    "fmt"
    "reflect"
)

// buildList constructs a list from values and random indices.
// randomIndices[i] is the 0-based index of the random target, or -1 for nil.
func buildList(values []int, randomIndices []int) *Node {
    if len(values) == 0 {
        return nil
    }

    nodes := make([]*Node, len(values))
    for i, v := range values {
        nodes[i] = &Node{Val: v}
    }
    for i := 0; i < len(nodes)-1; i++ {
        nodes[i].Next = nodes[i+1]
    }
    for i, idx := range randomIndices {
        if idx >= 0 {
            nodes[i].Random = nodes[idx]
        }
    }
    return nodes[0]
}

// listToSlice converts a list back to values and random indices for comparison.
func listToSlice(head *Node) ([]int, []int) {
    indexMap := make(map[*Node]int)
    idx := 0
    for cur := head; cur != nil; cur = cur.Next {
        indexMap[cur] = idx
        idx++
    }

    values := []int{}
    randoms := []int{}
    for cur := head; cur != nil; cur = cur.Next {
        values = append(values, cur.Val)
        if cur.Random != nil {
            randoms = append(randoms, indexMap[cur.Random])
        } else {
            randoms = append(randoms, -1)
        }
    }
    return values, randoms
}

func main() {
    // Build: 7 -> 13 -> 11 -> 10 -> 1
    // Randoms: nil, 0, 4, 2, 0
    original := buildList(
        []int{7, 13, 11, 10, 1},
        []int{-1, 0, 4, 2, 0},
    )

    copy1 := copyRandomList(original)
    copy2 := copyRandomListConstantSpace(original)

    origVals, origRand := listToSlice(original)
    c1Vals, c1Rand := listToSlice(copy1)
    c2Vals, c2Rand := listToSlice(copy2)

    fmt.Println("Original:", origVals, origRand)
    fmt.Println("Copy 1:  ", c1Vals, c1Rand)
    fmt.Println("Copy 2:  ", c2Vals, c2Rand)

    if reflect.DeepEqual(origVals, c1Vals) && reflect.DeepEqual(origRand, c1Rand) {
        fmt.Println("Hash map copy: PASS")
    } else {
        fmt.Println("Hash map copy: FAIL")
    }

    if reflect.DeepEqual(origVals, c2Vals) && reflect.DeepEqual(origRand, c2Rand) {
        fmt.Println("Constant space copy: PASS")
    } else {
        fmt.Println("Constant space copy: FAIL")
    }
}

Running this program should print matching values and random indices for all three lists, confirming that both approaches produce correct deep copies.

Best Practices and Common Pitfalls

When implementing this solution in Go, keep the following best practices in mind:

Always handle the nil head case explicitly. Returning nil early prevents nil pointer dereferences in subsequent loops.
Prefer the hash map approach for clarity. Unless memory constraints are severe, the map-based solution is easier to read, debug, and maintain.
Avoid sharing references. Ensure each copied node is freshly allocated with &Node{...}. Reusing original nodes defeats the purpose of a deep copy.
Test edge cases. Include lists with a single node, lists where all random pointers are nil, and lists where random pointers form cycles (a node's random points to itself).
Document mutation behavior. If you use the in-place approach, clearly document that the original list is temporarily modified, even if restored afterward.
Use map lookups for nil safety. Go maps return the zero value for missing keys, which elegantly handles nil random and next pointers without extra conditionals.

Performance Comparison

Both approaches run in linear time, but their constant factors differ. The hash map approach performs two passes with map insertions and lookups, which involve hashing pointer values. The in-place approach performs three passes with only pointer assignments. In practice, the hash map approach is often faster for small to medium lists due to simpler memory access patterns, while the in-place approach shines for very large lists where the map's memory overhead becomes significant.

Conclusion

The Copy List with Random Pointer problem is a deceptively simple exercise that rewards careful thinking about references, memory, and algorithm design. In Go, the explicit pointer semantics make the solution particularly instructive, as every reference assignment is visible in the code. Whether you choose the clarity of the hash map approach or the elegance of the in-place interweaving technique, mastering both will deepen your understanding of linked structures and prepare you for more complex graph cloning challenges. By following the step-by-step implementations and best practices outlined in this guide, you now have a reliable toolkit for solving this problem confidently in any Go codebase.