Copy a list with a random pointer

Deep-copy a list whose nodes carry a second, arbitrary 'random' pointer, without a dictionary mapping old nodes to new ones.

The idea

Weave a copy of every node right after its original, so a copy always sits exactly one step past its original. That makes each copy's random pointer easy to set: follow the original's random pointer and step one further to land on its copy. A final pass then unweaves the two lists back apart.

Code

public static Node CopyRandomList(Node head) {
    if (head == null) return null;
    for (Node n = head; n != null; n = n.next.next) {
        var copy = new Node(n.val);
        copy.next = n.next; n.next = copy;
    }
    for (Node n = head; n != null; n = n.next.next) {
        n.next.random = n.random?.next;
    }
    Node dummy = new Node(0), tail = dummy;
    for (Node n = head; n != null; n = n.next) {
        tail.next = n.next; tail = tail.next;
        n.next = n.next.next;
    }
    return dummy.next;
}

Tips

• The weave trick avoids an O(n) Dictionary<Node,Node> from original to copy — it gets you to O(1) extra space instead.
• random may point at any node, including null or the node itself; the weave handles both without a special case.

In the .NET library

A Dictionary<Node,Node> solution is easier to write and just as valid at O(n) time — reach for the weave only when the O(1)-space constraint actually matters.