Start learning free

LESSON 284 OF 347 · LINKED LISTS

Copy List with Random Pointer in C#: O(1) Extra Space by Interleaving

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 O(1) extra space.

STEP 1 OF 22

Guided

Ctrl + Enter to check

C# · LINKED LISTS

Copy List Random Pointer in C#, explained

Problem overview

Each ListNode has a val, a next pointer and a random pointer that leads to any node in the list or to null. CopyRandomList(head) must return a deep copy: n new nodes with the same values, whose next and random pointers go only to other new nodes. The input list must come back unchanged, and an empty list returns null.

In the first example, [[7,null],[13,0],[11,4],[10,2],[1,0]], each node is written as [val, random_index], so the 13 has its random pointer on the first node and the 11 has it on the last. The copy must have the same shape, inside the new list.

Approach: put each copy right after its original

The usual method keeps a dictionary from each original to its copy. That uses O(n) extra space. This lesson drops the dictionary by storing the mapping in the list's own structure: each copy is inserted directly after its original node. In a list A, B, C the copies make A, A', B, B', C, C'.

Then the copy of any original X is simply X.next. To set a copy's random pointer, take the original's random target T, and the copy of T is T.next.

The algorithm has three passes:

Interleave. Insert a value-only copy after each original.
Set the random pointers. For each original with a random target, set its copy's random to the target's copy.
Separate. Unweave the two lists, restoring the original and linking the copies to each other.

Step by step

Handle the empty list. If head is null, return null. Later code reads head.next, which would fail.
Start a cursor. node begins at head and is declared with var, which lets C# infer the type ListNode.
Loop while node != null. Each iteration inserts one copy.
Save the successor. nextNode = node.next, because the next line overwrites node.next.
Make the copy. copyNode is a new node with the same value. Its random pointer waits until every copy exists.
Splice it in. node.next now points to the copy.
Chain the copy onward. copyNode.next = nextNode, so the interleaved chain continues. For the last original, nextNode is null and the last copy ends the chain.
Jump over the copy. Move node to nextNode. Moving to node.next would land on the copy and insert copies of copies forever.
Reset the cursor to head for the second pass.
Loop again. This time node visits only the originals, because each iteration skips the copy.
Grab the copy. It is node.next.
Set its random. If node.random exists, the copy's random is node.random.next, the copy that sits right after the target.
Jump to the next original, copyNode.next.
Remember the new head, head.next, before the third pass changes head.next back.
Reset the cursor to head.
Loop a third time to separate the lists.
Take the copy after node.
Remember the next original as copyNode.next, before any link is changed.
Link the copies. If that next original exists, copyNode.next becomes its copy, nextNode.next. For the last pair, the last copy's next is already null.
Restore the original. node.next = nextNode undoes the interleaving, so the caller's list is unchanged.
Advance to nextNode.
Return newHead.

The solution in C#

class Solution {
    public ListNode CopyRandomList(ListNode head) {
        if (head == null) {
            return null;
        }

        var node = head;
        while (node != null) {
            var nextNode = node.next;
            var copyNode = new ListNode(node.val);
            node.next = copyNode;
            copyNode.next = nextNode;
            node = nextNode;
        }

        node = head;
        while (node != null) {
            var copyNode = node.next;
            if (node.random != null) {
                copyNode.random = node.random.next;
            }
            node = copyNode.next;
        }

        var newHead = head.next;
        node = head;
        while (node != null) {
            var copyNode = node.next;
            var nextNode = copyNode.next;
            if (nextNode != null) {
                copyNode.next = nextNode.next;
            }
            node.next = nextNode;
            node = nextNode;
        }

        return newHead;
    }
}

A few C# details are worth a closer look:

var is still static typing. The compiler infers ListNode from the right-hand side, and the variable has that type for good. It must be initialized in the same statement.
Repeated names are fine. copyNode and nextNode are declared in several loop bodies. Each loop body is its own scope, so the names don't clash. C# only rejects a name that is already declared in an enclosing scope.
Everything is a reference. nextNode and copyNode point to nodes and don't copy them, so a change made through copyNode.next changes the list itself.
The random field can be null, so reading node.random.next needs the if. Without it, a NullReferenceException follows.

Tracing a tiny list

Take A -> B where A's random is B. After pass one: A, A', B, B'. In pass two, A's random is B, so A'.random = B.next = B'. B has no random. In pass three, with node = A, the copy is A', the next original is B, and A' is linked to B' (B.next). Then A is linked back to B. The next round, B' is linked to nothing, since its successor is null, and B.next becomes null. The result is the original A -> B and the copy A' -> B' with A'.random = B'.

Complexity

Time: O(n). Three passes, each visiting every original node once with a constant amount of work per node.

Extra space: O(1). The only extra memory is a few variables. The n new nodes are the output itself. This beats the dictionary solution's O(n) extra space, at the cost of more delicate pointer work.

Edge cases and common mistakes

Empty list. The first if returns null before anything reads head.next.
A single node. It might point its random at itself. Pass one makes A, A', pass two sets A'.random = A.next = A', and pass three separates them again.
Setting randoms before all copies exist. The second pass must start only after the first has finished, since a random can point forward.
Using node.next instead of nextNode in pass one. It lands on the new copy and loops without end.
Forgetting to restore the input. The caller still owns the original list, and a skipped node.next = nextNode leaves copies woven into it.
Reading head.next too late. After the third pass, head.next is the original second node again, so newHead is captured first.
Copying the random pointer directly. copyNode.random = node.random would point the copy into the original list.

Testing

[[7,null],[13,0],[11,4],[10,2],[1,0]] copies to the same pairs, and the input still has its original pointers afterward.
[[1,1],[2,1]] copies to [[1,1],[2,1]].
[[3,null],[3,0],[3,null]] copies to the same pairs.
[] returns null.

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free