Clone Random Pointer Linked List

You are given a head of a linked list of length n such that each node contains an additional random pointer. This random pointer may point to any other node in the list or is null.

Create a deep copy of the given linked list, and return its head such that no additional space is used. The deep copy should consist of exactly n brand new nodes. Each new node must have the following properties: - Its value is set to the value of its corresponding original node. - Both the next and random pointers of the new node 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.

Constraints

• 0 <= n <= 1000
• 104 <= Node.val <= 104
• Node.random is null or points to some node in the linked list.

Solution Walkthrough

The problem seems simple, you just have to clone a linked list right? But there are two particular things to note here. One, there is an extra random pointer associated with each node in the list. Two, there is a constraint that no additional space should be used. A simple, brute-force solution seems easy, but our second constraint might not work well with it. Let's discuss this.

A Simple Solution

Copying a linked list is an easy task. Copy the head node, then create a new node with the same value as its corresponding node in the original list. Then, set the next pointer of the node to the newly created node, and by repeating this process, you can copy all nodes. On the other hand, dealing with the random pointer of the linked list is a little tricky. For each node, we need to remember where the random pointer points to. This means we need to save information, and for that, we can use hashmaps to remember the copied nodes. Essentially, there are just two steps:

1. Create a copy of all the nodes of the linked list. Fill the hashmap for each node by saving its information
2. Traverse through the copied list, and set the random pointer of each node according to the hashmap.

copyHead = Node(head.val)

while currentNode:
    newNode = Node(currentNode.val)
    hashmap[currentNode] = newNode
    currentNode = currentNode.next

Now, this approach seems fine, but there is one problem. Using a hashmap would mean we are using additional space of O(n). That does not fit well with the constraint of our problem, which requires us to solve without using any additional space.

This problem can be solved without using hashmap in O(n) space complexity by shifting pointers.

Space Efficient Solution

So now we cannot use any extra lists or hashmaps that would increase the space complexity. What do we do in this case?

Well, let's assume that the linked list is not read-only, but we can modify it as well. The idea is to add new nodes to the list and shift pointers such that the new nodes point to each other in the same state as the original list. In other words,

• Create a copy of the first node, and insert it between the first and second node of the original list. Now create a copy of the second node, and insert it between the second and third node. Add duplicate nodes in this fashion for the entire list.
• Next, copy the random pointer of each node, and make them point to other nodes in the same way as the original list.
• Finally, separate the original and duplicate nodes by adjusting the pointers in the following manner (the next pointer will move to skip a node to point to the original list node, same for copy list). originalList.next = originalList.next.next; copyList.next = copyList.next.next;

Time Complexity

The entire linked list is traversed thrice, so the time complexity will be O(n) + O(n) + O(n), which amounts to O(n).

Consider that the given linked list is read-only, and it cannot be modified. The space complexity of the problem in this case would be ______.

The proposed solution iterates through the linked list thrice. Can you solve the problem in two iterations? If so, how?

One Pager Cheat Sheet

• Create a deep copy of the given linked list using no additional space, consisting of exactly n new nodes such that each new node's value, next and random pointers represent an exact duplicate of the original list.
• Cloning a Linked List with an associated random pointer, while using no additional space, causes an interesting challenge.
• Copying a linked list is easy when dealing with the head node, but the random pointer can be tricky and requires a hashmap if additional space of O(n) needs to be avoided.
• We can solve this problem in O(n) space complexity using pointers and storing the current node's random pointer in its cloned node's next pointer.
• We can modify the original list by creating copies of its nodes, then adjusting pointers and separating them, to clone the list and maintain the same state.
• The time complexity of the task is O(n).
• The given read-only linked list requires O(n) space and time complexity to traverse.
• Duplicates can be found in a linked list in two iterations by storing the count of each value in a hashmap and returning values whose count is greater than or equal to 2, reducing the required space complexity to O(n).