Copy List with Random Pointer - Java Solution

1. Introduction

This blog post delves into the "Copy List with Random Pointer" problem, a complex challenge in linked list manipulation that tests deep copying skills and understanding of pointer manipulation. The task is to create a deep copy of a linked list where each node has a random pointer that could point to any node in the list or be null.

Problem

Given a linked list where each node contains an additional random pointer, the objective is to construct a deep copy of the list. Each new node in the copied list should have its value set to the value of its corresponding original node, with next and random pointers pointing to nodes in the copied list, ensuring no pointers point to nodes in the original list.

2. Solution Steps

1. Iterate through the original list and create a copy of each node, placing each new node next to its original node. This helps to map the original nodes to their copies for random pointer assignment.

2. Iterate again to set up the random pointers in the copied nodes.

3. Restore the original list and separate the copied list from it.

4. Return the head of the copied list.

3. Code Program

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class CopyListWithRandomPointer {
    public static void main(String[] args) {
        // Example use case
        // Create the list here and call copyRandomList
    }

    // Function to copy a list with a random pointer
    public static Node copyRandomList(Node head) {
        if (head == null) return null;

        // Step 1: Creating new nodes alongside original nodes
        Node current = head;
        while (current != null) {
            Node newNode = new Node(current.val);
            newNode.next = current.next;
            current.next = newNode;
            current = newNode.next;
        }

        // Step 2: Assigning random pointers to the new nodes
        current = head;
        while (current != null) {
            if (current.random != null) {
                current.next.random = current.random.next;
            }
            current = current.next.next;
        }

        // Step 3: Separating the two lists
        current = head;
        Node newHead = head.next;
        Node copyCurrent = newHead;
        while (current != null) {
            current.next = current.next.next;
            copyCurrent.next = (copyCurrent.next != null) ? copyCurrent.next.next : null;
            current = current.next;
            copyCurrent = copyCurrent.next;
        }

        return newHead;
    }
}

Output:

// Output depends on the specific linked list input and is not provided in the example

Explanation:

1. copyRandomList: This function creates a deep copy of a linked list with a random pointer.

2. It first creates a new node for each original node and places it next to its original node. This interleaving helps in setting up the random pointers accurately in the second iteration.

3. In the second iteration, the function assigns the random pointers to the new nodes. Since each new node is adjacent to its original node, the corresponding random pointer can be assigned easily.

4. The third step involves separating the copied nodes from the original nodes, restoring the original list and extracting the copied list.

5. The function returns the head of the newly copied list.

6. This approach efficiently copies the list with random pointers without needing extra space for a hash map.