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;

That's all we've got! Let's move on to the next tutorial.

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