Copy List with Random Pointer

class Solution {
public:
    Node* cloneListWithRandomPointer(Node* original_head) {
        if (!original_head) {
            return nullptr;
        }

        Node* current = original_head;
        while (current != nullptr) {
            Node* clone = new Node(current->val, nullptr, nullptr);
            clone->next = current->next;
            current->next = clone;
            current = clone->next;
        }

        current = original_head;
        while (current != nullptr) {
            current->next->random = current->random ? current->random->next : nullptr;
            current = current->next->next;
        }

        Node* old_list = original_head;
        Node* new_list = original_head->next;
        Node* new_head = original_head->next;
        while (old_list != nullptr) {
            old_list->next = old_list->next->next;
            new_list->next = new_list->next ? new_list->next->next : nullptr;
            old_list = old_list->next;
            new_list = new_list->next;
        }

        return new_head;
    }
};

This solution outlines how to clone a linked list where each node contains an additional pointer to a random node in the list. The function cloneListWithRandomPointer implements this operation in C++. Here’s a breakdown of the method used:

• Firstly, traverse the original linked list to create a new node for each existing node. Insert these new nodes directly after their corresponding original nodes.
• Next, assign the random pointer of each new node. This is done by setting it to the random pointer of the original node's next node, taking care to check if the original node's random pointer is null.
• Finally, separate the interleaved list of original and new nodes. This involves correcting the next pointers of both the original and the copied nodes to restore the original list and to finish forming the separate cloned list.

The outcome is a new linked list where each node from the original list is duplicated with both the next and random pointers correctly assigned, effectively deep copying the initial list with its random pointer structure intact.

Ensure following this explanation allows for an understanding of manipulating complex data structures, such as linked lists with additional pointer tracking.

public class Solution {
    public Node cloneRandomLinkedList(Node originalHead) {
        if (originalHead == null) {
            return null;
        }

        Node current = originalHead;
        while (current != null) {
            Node clonedNode = new Node(current.val);

            clonedNode.next = current.next;
            current.next = clonedNode;
            current = clonedNode.next;
        }

        current = originalHead;

        while (current != null) {
            current.next.random = (current.random != null) ? current.random.next : null;
            current = current.next.next;
        }

        Node originalCurrent = originalHead;
        Node clonedCurrent = originalHead.next;
        Node clonedHead = originalHead.next;

        while (originalCurrent != null) {
            originalCurrent.next = originalCurrent.next.next;
            clonedCurrent.next = (clonedCurrent.next != null)
                ? clonedCurrent.next.next
                : null;
            originalCurrent = originalCurrent.next;
            clonedCurrent = clonedCurrent.next;
        }
        return clonedHead;
    }
}

The provided Java code defines a method cloneRandomLinkedList within the Solution class, which is designed to clone a complex linked list where each node has a next pointer and a random pointer. The task involves deep copying a list such that the new list is a standalone copy of the original list with the same val, next, and random connections.

Below is the step-by-step approach taken in the code to accomplish this:

1. The method first checks if the input head node, originalHead, is null. If it is, it returns null indicating there are no nodes to duplicate.
2. Define current to traverse the original list. Iterate through the list:
   • Create a new node, clonedNode, for each original node mirroring the val.
   • Insert the cloned node just after the original node by adjusting the next pointers, effectively weaving the cloned nodes among the original nodes.
3. Set current back to originalHead to start the second pass through the list:
   • Assign the random pointer of each cloned node. This is achieved by pointing it to the next of the random pointed node of the original, if the random pointer is not null.
4. Initialize pointers to handle separation of the original and cloned list:
   • originalCurrent points to the beginning of the intertwined list.
   • clonedCurrent and clonedHead point to the head of the cloned list.
5. Decouple the original and cloned lists:
   • Advance originalCurrent and clonedCurrent through their respective lists resetting the next pointers to restore the original list and to finalize the separate cloned list.

This method uses space efficiently by avoiding the use of extra space for a map typically used to keep track of cloned nodes vis-a-vis their corresponding original nodes. The node intertwining and later separation technique ensures both lists are properly set up with correct pointers, all within a linear time complexity relative to the number of nodes in the original list.

struct Node* createNode(int value, struct Node* nextNode, struct Node* randomPointer) {
    struct Node* tempNode = (struct Node*)malloc(sizeof(struct Node));
    tempNode->val = value;
    tempNode->next = nextNode;
    tempNode->random = randomPointer;
    return tempNode;
}

struct Node* cloneLinkedListWithRandomPointer(struct Node* originalHead) {
    if (!originalHead) {
        return NULL;
    }

    struct Node* traverse = originalHead;
    while (traverse) {
        struct Node* clonedNode = createNode(traverse->val, NULL, NULL);
        clonedNode->next = traverse->next;
        traverse->next = clonedNode;
        traverse = clonedNode->next;
    }

    traverse = originalHead;
    while (traverse) {
        traverse->next->random = (traverse->random) ? traverse->random->next : NULL;
        traverse = traverse->next->next;
    }

    struct Node* oldListPointer = originalHead;
    struct Node* newListPointer = originalHead->next;
    struct Node* clonedHead = originalHead->next;
    while (oldListPointer) {
        oldListPointer->next = oldListPointer->next->next;
        newListPointer->next = (newListPointer->next) ? newListPointer->next->next : NULL;
        oldListPointer = oldListPointer->next;
        newListPointer = newListPointer->next;
    }

    return clonedHead;
}

The provided C code tackles the problem of duplicating a linked list where each node possesses an additional random pointer apart from the standard next pointer. The solution involves creating a deep copy of the list, ensuring that the random links between nodes are accurately reproduced in the new list.

• The first function, createNode, is a helper function to initialize and allocate memory for a new node when given a value, a pointer to the next node, and a pointer to a random node.

• The main function, cloneLinkedListWithRandomPointer, begins by handling the edge case where the input list is empty, returning NULL if so.

• Next, it loops through the original list, inserting a cloned node immediately after each original node. This is achieved by:

  1. Allocating a new node for each original node using createNode.
  2. Adjusting next pointers to include the newly created clone node right after the original one.

• Following the clone insertion, the code proceeds to assign the random pointers for each of the cloned nodes. It does this in a second traversal of the list, ensuring each cloned node's random points to the subsequent node of its counterpart's random pointer if it exists; otherwise, it is set to NULL.

• Finally, the function extracts the cloned nodes to form a new list. It adjusts the next pointers of both original and cloned nodes:

  1. Setting the original nodes' next to skip over their respective clones.
  2. Connecting the cloned nodes to each other correctly based on the original sequence.

• The sequence of links adjustments ensures that the original list remains intact, and a new list that mirrors the structure and random connections of the original is returned.

The approach carefully handles memory management and pointer adjustments to create a cloned list, which exactly replicates the complicated connection schemas of the original.

var duplicateRandomList = function (origin) {
    if (origin === null) {
        return null;
    }
    let current = origin;
    while (current !== null) {
        let copied = new Node(current.val, null, null);
        copied.next = current.next;
        current.next = copied;
        current = copied.next;
    }
    current = origin;
    while (current !== null) {
        current.next.random = current.random !== null ? current.random.next : null;
        current = current.next.next;
    }
    let oldList = origin; // Original nodes list
    let newList = origin.next; // Copied nodes list
    let savedHead = origin.next;
    while (oldList !== null) {
        oldList.next = oldList.next.next;
        newList.next = newList.next !== null ? newList.next.next : null;
        oldList = oldList.next;
        newList = newList.next;
    }
    return savedHead;
};

This JavaScript solution addresses the problem of duplicating a linked list where each node has a next pointer and a random pointer that can point to any node in the list or null.

Here's a breakdown of how the solution works:

1. First, check if the input list, origin, is null. If it is, return null since there is no list to copy.

2. Iterate through the original list and for each node, create a new node with the same value. Insert these new nodes right after their corresponding original nodes. This interleaving of old and new nodes helps keep track of the random pointers in the subsequent steps.

3. Once the new nodes are inserted, iterate through the list again to update the random pointers of the new nodes. For each original node's random pointer, point the corresponding new node's random to the new node of the original random's target. This step effectively clones the random linkage between nodes.

4. Separate the interleaved list into the original list and the copied list. Initialize two pointers, oldList for traversing the original nodes, and newList for traversing the new nodes. Adjust the next pointers for both lists to extract the copied list while restoring the original list's structure.

5. Finally, return the head of the new list, savedHead, which is a fully duplicated list mirroring the original list with both next and random pointers correctly set.

This approach efficiently clones the list in linear time complexity with constant space complexity, making it a robust solution for duplicating linked lists with complex internal linkages.

class Solution:
    def duplicateRandomList(self, head: "Optional[Node]") -> "Optional[Node]":
        if not head:
            return head

        # Creating intertwining of old and duplicated nodes
        current = head
        while current:

            # Create duplicate node
            duplicate = Node(current.val, None, None)

            # Place the duplicate node beside the original
            duplicate.next = current.next
            current.next = duplicate
            current = duplicate.next

        current = head

        # Set the 'random' pointer for the duplicate nodes
        while current:
            current.next.random = current.random.next if current.random else None
            current = current.next.next

        # Decouple the two interleaved linked lists
        old_ptr = head  # Original nodes path
        dup_ptr = head.next  # Duplicated nodes path
        dup_head = head.next
        while old_ptr:
            old_ptr.next = old_ptr.next.next
            dup_ptr.next = dup_ptr.next.next if dup_ptr.next else None
            old_ptr = old_ptr.next
            dup_ptr = dup_ptr.next
        return dup_head

This Python function efficiently duplicates a linked list where each node contains an additional random pointer that might point to any node within the list or be null. The strategy implemented here involves three main steps:

1. Interweave the original list with cloned nodes:

   • Traverse the original list and create a new node for each existing node.
   • Insert each new node directly after its corresponding original node, modifying the next pointers accordingly.

2. Establish correct random pointers for the cloned nodes:

   • Again traverse the list. For each original node's cloned node, set the random pointer by using the original node's random pointer.
   • The key is to assign the cloned random pointer to point to the next node of the original random pointer. This handles cases whether the original random pointer is null.

3. Separating the intertwined lists into two independent lists:

   • Initialize two pointers, one for the original list and one for the clone, then iterate through the intertwined list, appropriately adjusting the next pointers to decouple the original nodes from their clones.

During this entire procedure, the function ensures that the structural integrity of the original list is maintained, and each cloned node is correctly linked, both through the next and random pointers. The function returns the head of the copied list, which facilitates further operations on the duplicated structure without affecting the original list. This in-place solution adds efficiency in terms of space, working without the need for additional data structures for mapping old nodes to their duplicates.