NUHMAN.com

Introduction

LeetCode 138: Copy List with Random Pointer challenges you to deeply clone a linked list where each node has an additional pointer called random, which can point to any node in the list or be nil.

This problem helps you master techniques in linked list traversal, deep copy, and pointer manipulation.

Problem Statement

You are given a special linked list where each node contains:

• An integer val
• A pointer next to the next node
• A pointer random to any node (or nil)

Your task is to return a deep copy of the list.

Example:

css

Input:
    Node1(val=7) -> Node2(val=13) -> Node3(val=11) ...
    Random pointers: 13 → 7, 11 → 1, etc.

Output:
    A deep copy of the original list with identical structure and random pointers.

Approach

There are two popular solutions:

✅ Approach 1: Hash Map (Simpler, Extra Space)

1. First pass: Create a mapping of old nodes to new nodes.
2. Second pass: Assign next and random pointers using the map.

✅ Approach 2: In-Place Interleaving (No Extra Space)

1. First pass: For each original node, insert its copy directly after it.
2. Second pass: Set the random pointer of each copy.
3. Third pass: Restore the original list and extract the deep copy.

We’ll implement Approach 2, which is clever, elegant, and uses O(1) space.

Go Implementation

go

package main

import "fmt"

type Node struct {
    Val    int
    Next   *Node
    Random *Node
}

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }

    // Step 1: Interleave original and copied nodes
    for curr := head; curr != nil; {
        next := curr.Next
        copy := &Node{Val: curr.Val}
        curr.Next = copy
        copy.Next = next
        curr = next
    }

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

    // Step 3: Separate the two lists
    dummy := &Node{}
    copyCurr, curr := dummy, head
    for curr != nil {
        next := curr.Next.Next

        copy := curr.Next
        copyCurr.Next = copy
        copyCurr = copy

        curr.Next = next
        curr = next
    }

    return dummy.Next
}

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

• Time: We pass through the list three times → O(n)
• Space: No extra space used besides a few pointers.

Why This Works

By interleaving the copied nodes right after the originals, we gain access to both the old and new nodes during traversal. This simplifies the setup of random pointers and allows us to avoid a hashmap, keeping space complexity constant.

Edge Cases

• Empty list (head == nil)
• List where random points to nil or the same node
• Only one node in the list

Conclusion

LeetCode 138: Copy List with Random Pointer is a great example of clever in-place manipulation. It teaches how to traverse and modify linked structures without additional memory, making it both a practical and elegant problem—perfect for coding interviews and mastering pointer-based logic in Go.