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.

1copyHead = Node(head.val)
2
3while currentNode:
4    newNode = Node(currentNode.val)
5    hashmap[currentNode] = newNode
6    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.

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).

1originalList.next = originalList.next.next;
2copyList.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).

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).

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function Node(val, next, random) {

    this.val = val;

    this.next = next;

    this.random = random;

};

​

function cloneRandomList(head) {

    if (head === null) {

        return null;

    }

​

    let currentNode = head;

    while (currentNode) {

        let temp = new Node(currentNode.val);

        temp.next = currentNode.next;

        currentNode.next = temp;

        currentNode = currentNode.next.next;

    }

​

    currentNode = head;

    while (currentNode) {

        if (currentNode.random) {

            currentNode.next.random = currentNode.random.next;

        } else {

            currentNode.next.random = null;

        }

        currentNode = currentNode.next.next;

    }

​

    currentNode = head;

Got more time? Let's keep going.

If you had any problems with this tutorial, check out the main forum thread here.