Start learning free

LESSON 278 OF 338 · LINKED LISTS

Copy List with Random Pointer in Go: O(n) with a Map

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

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 (null pointer), so return null.

 

Constraints:

  • 0 <= n <= 1000
  • -10000 <= Node.val <= 10000
  • Node.random is null 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

    GO · LINKED LISTS

    Copy List Random Pointer in Go, explained

    Problem overview

    The function copyRandomList receives the head of a linked list of *ListNode values. Besides Val and Next, every node has a Random pointer that may point to any node of the list, or be nil. The function must build a deep copy: exactly n brand-new nodes with the same values, where the Next and Random pointers of the copies point to copies, never to original nodes. It returns the head of the copy.

    Tests describe a list as pairs [val, random_index]. For [[7,null],[13,0],[11,4],[10,2],[1,0]], the node with value 13 has its random pointer on index 0, the node holding 7. The copy must have the same shape, with its own 13 pointing to its own 7. An empty list yields nil. The statement allows O(n) time and up to 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 Random: a node's random target can be earlier or later in the list, so when the copy of that node is created, the copy of its target may not exist yet.

    The fix is to split the work into two passes, with a map linking each original node to its copy:

    1. First pass: create a copy of every node, holding only the value, and record it in the map under the original node as the key.
    2. Second pass: now every original has a copy, so any pointer can be translated by a lookup. For each original node, set the copy's Next to the copy of node.Next and its Random to the copy of node.Random.

    The map has type map[*ListNode]*ListNode. Pointer keys compare by address, so two different nodes with the same value are different keys.

    The nil cases come out right without any if. The map holds no entry for nil, and reading a missing key from a Go map gives the zero value of the value type, which for a pointer is nil. So copies[node.Next] is nil for the last node, and copies[node.Random] is nil when there is no random target.

    Step by step

    1. Create the map with make(map[*ListNode]*ListNode), named copies. A map must be created before use: writing to a nil map panics.
    2. Declare node and start it at head, so head stays available for the second pass and the return value.
    3. Loop while node != nil. Go has no while; a for with a condition does the same.
    4. Store a new node: copies[node] = &ListNode{Val: node.Val}. The literal sets only Val, so Next and Random start as nil. They are filled in later, when all copies exist.
    5. Advance with node = node.Next. Without this line the loop never ends.
    6. Reset with node = head for the second pass.
    7. Loop again while node != nil.
    8. Wire Next: copies[node].Next = copies[node.Next].
    9. Wire Random: copies[node].Random = copies[node.Random]. The order of the two lines doesn't matter, because both only read the map.
    10. Advance along the original list, with node = node.Next. The pass walks the originals while it builds the copies' links.
    11. Return copies[head], the copy of the head. For an empty list head is nil, the lookup finds no entry, and the result is nil.

    The solution in Go

    func copyRandomList(head *ListNode) *ListNode {
	copies := make(map[*ListNode]*ListNode)
	node := head
	for node != nil {
		copies[node] = &ListNode{Val: node.Val}
		node = node.Next
	}
	node = head
	for node != nil {
		copies[node].Next = copies[node.Next]
		copies[node].Random = copies[node.Random]
		node = node.Next
	}
	return copies[head]
}

    Go details worth knowing:

    • Missing keys give the zero value. Reading copies[k] for a key that isn't in the map returns nil here and doesn't panic. When you need to tell "absent" from "present with the zero value", use v, ok := copies[k]. This solution doesn't need it, because the absent key and a nil pointer mean the same thing.
    • Assigning to a field of a map value. copies[node].Next = ... compiles because the map's values are pointers: the expression copies[node] is a *ListNode, and its field can be assigned through the pointer. With a map of struct values (not pointers), Go would reject such an assignment.
    • Reading a nil map is fine, writing is not. A nil map returns zero values on reads, but copies[node] = ... on one panics with assignment to entry in nil map. That is why make comes first.
    • Reusing a variable. The second pass assigns node = head to the variable that the first pass left at nil. It is a new walk, not a new declaration.

    Complexity

    Time: O(n). Each pass visits every node once, and each map operation takes constant time on average.

    Space: O(n). The map holds one entry per node, on top of the n new nodes that the problem requires anyway. The copy itself is unavoidable. The extra cost of the approach is the map, and the other lesson on this problem removes it.

    Edge cases and common mistakes

    • Empty list. The loops don't run, and copies[head] is nil.
    • Random pointer to itself or to a later node. The two-pass structure handles both, since all copies exist before any pointer is wired. A single pass that creates copies on demand would need extra care here.
    • Random is nil. copies[nil] is nil, so the copy's Random stays nil.
    • Equal values. For [[3,null],[3,0],[3,null]], the three nodes all hold 3, but they are different keys, so each random pointer lands on the correct copy. Keying the map by value would break this.
    • Sharing nodes with the original. Copying a pointer, such as copies[node].Random = node.Random, leaves the copy pointing into the original list, which the statement forbids.
    • Forgetting node = head. After the first loop node is nil, so the second loop would do nothing and the copy would have no links.

    Testing

    • [[7,null],[13,0],[11,4],[10,2],[1,0]] gives the same description, built from new nodes.
    • [[1,1],[2,1]] gives [[1,1],[2,1]].
    • [[3,null],[3,0],[3,null]] gives [[3,null],[3,0],[3,null]].
    • [] gives [].
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free