Logo for ammarahmed.ca
Medium
Jul 27, 2025
#linked-list

138. Copy List with Random Pointer

Problem

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

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 representing Node.val
    • random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

      Your code will only be given the head of the original linked list.

      Example 1:

      1Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 2Output: [[7,null],[13,0],[11,4],[10,2],[1,0]] 3

      Example 2:

      1Input: head = [[1,1],[2,1]] 2Output: [[1,1],[2,1]] 3

      Example 3:

      1Input: head = [[3,null],[3,0],[3,null]] 2Output: [[3,null],[3,0],[3,null]] 3

      Constraints:

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

            Approach

            To solve this problem, we can create mapping from old nodes to new nodes and then use the old nodes when creating the random connections in the new nodes.

            To start, we'll create a new list that has old and new nodes interweaved. i.e.: 7 -> 7' -> 13 -> 13' -> 11 -> 11' -> 10 -> 10' -> 1 -> 1' -> nil.

            From this, we can iterate over only the old nodes and set the connections on the curr.Next.Random (new node) to be curr.Random.Next because the next node will always be the corresponding new node.

            After this, we remove the old nodes and re-construct the old list.

            Complexity

            Time: O(n)

            We iterate over the input array once, many times.

            Space: O(1)

            The only extra space created is for the result.

            Solution

            1func copyRandomList(head *Node) *Node { 2 // Create the interweaved list, oldNode -> newNode 3 dummy := &Node{} 4 curr := head 5 tail := dummy 6 for curr != nil { 7 curr.Next = &Node{ 8 Val: curr.Val, 9 Next: curr.Next, 10 } 11 tail.Next = curr 12 tail = tail.Next.Next 13 curr = curr.Next.Next 14 } 15 16 // Create the random connections 17 curr = dummy.Next 18 for curr != nil { 19 if curr.Random != nil { 20 curr.Next.Random = curr.Random.Next 21 } else { 22 curr.Next.Random = nil 23 } 24 25 curr = curr.Next.Next 26 } 27 28 // Remove the old nodes 29 curr = dummy 30 for curr != nil && curr.Next != nil { 31 if curr.Next != nil { 32 tmp := curr.Next // Save the old node 33 curr.Next = curr.Next.Next 34 tmp.Next = tmp.Next.Next // Re-construct the old list 35 } else { 36 curr.Next = nil 37 } 38 curr = curr.Next 39 } 40 41 return dummy.Next 42} 43