Logo for ammarahmed.ca
Medium
Feb 17, 2026
#linked-list

138. Copy List with Random Pointer

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]]

      Example 2:

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

      Example 3:

      1Input: head = [[3,null],[3,0],[3,null]] 2Output: [[3,null],[3,0],[3,null]]
      • 0 <= n <= 1000
        • -104 <= Node.val <= 104
          • Node.random is null or is pointing to some node in the linked list.

            Constraints:

            Notes

            Intuition

            Interweave new nodes into the original list so that the next pointer of the old list points to the corresponding new node, making assigning random pointers trivial by the next node.

            Implementation

            Start by interveaving the new nodes into the original list (i.e. old1 -> new1 -> old2 -> new2 -> etc.). Iterate over the original list, save the next node in a temporary variable (next), set curr.next to the new node with the current value and next pointing to next, set curr = next.

            After the interweaving is complete, we want to iterate again and assign the random pointers. Iterate starting from head while curr and curr.next. If curr (old) has a random pointer (not null), set curr.next.random (new node's random) to curr.random.next (old node's random -> next, which is the new node).

            After the random pointers are assigned, we simply need to construct the resultant list by starting from head.next (first new node) and skipping over each next node(old node). The resultant list will be stored in head.next.

            • Time: O(n) - iterate over the original list 3 times, sequentially (interweaving, random pointers, result)
              • Space: O(1) - no extra space created

                Complexity

                Solution

                1from typing import Optional 2 3# Definition for a Node. 4class Node: 5 def __init__(self, x: int, next: Optional['Node']= None, random: Optional['Node']= None): 6 self.val = int(x) 7 self.next = next 8 self.random = random 9 10class Solution: 11 def copyRandomList(self, head: Optional[Node]) -> Optional[Node]: 12 # interweave new nodes 13 # i.e old1 -> new1 -> old2 -> new2 -> etc. 14 curr = head 15 while curr: 16 next = curr.next 17 curr.next = Node(curr.val, next) 18 curr = next 19 20 # assign random pointers 21 curr = head 22 while curr and curr.next: 23 if curr.random: 24 curr.next.random = curr.random.next 25 curr = curr.next.next 26 # construct resultant list 27 curr = head.next if head else None 28 while curr and curr.next: 29 curr.next = curr.next.next 30 curr = curr.next 31 return head.next if head else None 32 33 34 35 36 37if __name__ == "__main__": 38 # Include one-off tests here or debugging logic that can be run by running this file 39 # e.g. print(solution.two_sum([1, 2, 3, 4], 3)) 40 solution = Solution() 41 input = [[7,None],[13,0],[11,4],[10,2],[1,0]] 42 nodes = [Node(val) for val, _ in input] 43 for i, (_, random_index) in enumerate(input): 44 if i < len(nodes) - 1: 45 nodes[i].next = nodes[i + 1] 46 if random_index is not None: 47 nodes[i].random = nodes[random_index] 48 49 head = nodes[0] if nodes else None 50 solution.copyRandomList(head) 51