Clone Linked List with Random Pointer in DSA Javascript - Time & Space Complexity

Time Complexity: Clone Linked List with Random Pointer

O(n)

Understanding Time Complexity

We want to understand how the time needed to clone a linked list with random pointers grows as the list gets bigger.

Specifically, how many steps does it take to copy all nodes and their random links?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function cloneLinkedList(head) {
  if (!head) return null;

  // Step 1: Insert cloned nodes after original nodes
  let current = head;
  while (current) {
    let copy = { val: current.val, next: current.next, random: null };
    current.next = copy;
    current = copy.next;
  }

  // Step 2: Assign random pointers for cloned nodes
  current = head;
  while (current) {
    if (current.random) {
      current.next.random = current.random.next;
    }
    current = current.next.next;
  }

  // Step 3: Separate cloned list from original
  current = head;
  let copyHead = head.next;
  while (current) {
    let copy = current.next;
    current.next = copy.next;
    copy.next = copy.next ? copy.next.next : null;
    current = current.next;
  }

  return copyHead;
}
    

This code clones a linked list where each node has a next and a random pointer, creating a new list with the same structure.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Three separate while loops that each go through all nodes once.
• How many times: Each loop runs once over all n nodes, so about 3 x n steps total.

How Execution Grows With Input

As the list size grows, the number of steps grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 30 steps (3 x 10)
100	About 300 steps (3 x 100)
1000	About 3000 steps (3 x 1000)

Pattern observation: The steps increase linearly as the list gets longer.

Final Time Complexity

Time Complexity: O(n)

This means the time to clone the list grows directly with the number of nodes.

Common Mistake

[X] Wrong: "Because there are three loops, the time complexity is O(n³)."

[OK] Correct: Each loop runs one after another, not nested inside each other, so their times add up, not multiply.

Interview Connect

Understanding this linear time cloning method shows you can handle complex pointer structures efficiently, a useful skill in many coding challenges.

Self-Check

"What if the random pointers could point to any node in a separate list? How would that affect the time complexity?"

Practice

1. What is the main challenge when cloning a linked list with a random pointer?

easy

A. Reversing the linked list before cloning

B. Copying the values of the nodes only

C. Maintaining the correct random pointer references in the cloned list

D. Sorting the linked list nodes before cloning

Solution

1. Step 1: Understand the linked list structure

   A linked list with random pointers has two references per node: next and random. Cloning must preserve both.

2. Step 2: Identify the cloning challenge

   While copying next pointers is straightforward, random pointers can point anywhere, so they must be carefully mapped to cloned nodes.

3. Final Answer:

   Maintaining the correct random pointer references in the cloned list -> Option C

4. Quick Check:

   Random pointer cloning = main challenge [OK]

Hint: Focus on copying random pointers correctly [OK]

Common Mistakes:

• Ignoring random pointers during cloning
• Assuming random pointers follow next pointers
• Copying only node values without pointers

2. Which of the following JavaScript code snippets correctly creates a new node with value `val` and initializes its `next` and `random` pointers to null?

easy

A. function Node(val) { this.value = val; this.next = null; this.random = null; }

B. function Node(val) { this.val = val; this.next = val; this.random = val; }

C. function Node(val) { this.val = val; this.next = undefined; this.random = undefined; }

D. function Node(val) { this.val = val; this.next = null; this.random = null; }

Solution

1. Step 1: Check property names and initialization

   The node should have properties named val, next, and random. Both next and random should start as null.

2. Step 2: Verify code correctness

   function Node(val) { this.val = val; this.next = null; this.random = null; } correctly assigns val and sets next and random to null. Others either use wrong property names or incorrect initial values.

3. Final Answer:

   function Node(val) { this.val = val; this.next = null; this.random = null; } -> Option D

4. Quick Check:

   Correct node constructor = function Node(val) { this.val = val; this.next = null; this.random = null; } [OK]

Hint: Use null for uninitialized pointers in node constructor [OK]

Common Mistakes:

• Using wrong property names like value instead of val
• Initializing pointers with val instead of null
• Using undefined instead of null for pointers

3. Given the following code snippet to clone a linked list with random pointers, what will be the output of the console.log after cloning?

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

// Original list: 1 -> 2 -> null
const node1 = new Node(1);
const node2 = new Node(2);
node1.next = node2;
node1.random = node2;
node2.random = node2;

function cloneList(head) {
  if (!head) return null;
  const map = new Map();
  let curr = head;
  while (curr) {
    map.set(curr, new Node(curr.val));
    curr = curr.next;
  }
  curr = head;
  while (curr) {
    map.get(curr).next = map.get(curr.next) || null;
    map.get(curr).random = map.get(curr.random) || null;
    curr = curr.next;
  }
  return map.get(head);
}

const clonedHead = cloneList(node1);
console.log(clonedHead.val, clonedHead.next.val, clonedHead.random.val);

medium

A. 1 2 1

B. 1 2 2

C. 1 1 2

D. 2 1 2

Solution

1. Step 1: Understand the original list structure

   Node1.val=1, Node2.val=2; node1.next=node2; node1.random=node2; node2.random=node2.

2. Step 2: Trace cloning and pointer assignments

   Cloned node1 has val=1, next points to cloned node2 (val=2), random points to cloned node2 (val=2).

3. Final Answer:

   1 2 2 -> Option B

4. Quick Check:

   Cloned list values = 1 2 2 [OK]

Hint: Map original nodes to clones to fix random pointers [OK]

Common Mistakes:

• Confusing random pointer values
• Not mapping random pointers correctly
• Printing original node values instead of cloned

4. The following code attempts to clone a linked list with random pointers but has a bug. What is the bug?

function cloneList(head) {
  if (!head) return null;
  let curr = head;
  const map = new Map();
  while (curr) {
    map.set(curr, new Node(curr.val));
    curr = curr.next;
  }
  curr = head;
  while (curr) {
    map.get(curr).next = map.get(curr.next);
    map.get(curr).random = curr.random;
    curr = curr.next;
  }
  return map.get(head);
}

medium

A. Random pointers are assigned to original nodes instead of cloned nodes

B. Next pointers are not assigned at all

C. Map is not used to store cloned nodes

D. Function returns null always

Solution

1. Step 1: Analyze random pointer assignment

   map.get(curr).random = curr.random assigns original node's random pointer, not cloned node's.

2. Step 2: Identify correct assignment

   It should be map.get(curr).random = map.get(curr.random) to assign cloned random pointer.

3. Final Answer:

   Random pointers are assigned to original nodes instead of cloned nodes -> Option A

4. Quick Check:

   Random pointer assignment bug = Random pointers are assigned to original nodes instead of cloned nodes [OK]

Hint: Always map random pointers to cloned nodes [OK]

Common Mistakes:

• Assigning random pointers directly from original nodes
• Forgetting to map next pointers
• Not initializing map before use

5. You want to clone a linked list with random pointers without using extra space (no hash maps). Which approach correctly describes the process?

hard

A. Interleave cloned nodes between original nodes, assign random pointers, then separate the lists

B. Create a new list by copying values only, ignoring random pointers

C. Use recursion to clone nodes and random pointers simultaneously

D. Reverse the original list, clone nodes, then reverse back

Solution

1. Step 1: Interleave cloned nodes

   Insert cloned nodes right after each original node, so list looks like original1 -> clone1 -> original2 -> clone2 -> ...

2. Step 2: Assign random pointers and separate lists

   Set clone.random = original.random.next, then detach cloned nodes to form the cloned list.

3. Final Answer:

   Interleave cloned nodes between original nodes, assign random pointers, then separate the lists -> Option A

4. Quick Check:

   Interleaving method = Interleave cloned nodes between original nodes, assign random pointers, then separate the lists [OK]

Hint: Interleave clones to avoid extra space [OK]

Common Mistakes:

• Ignoring random pointers in cloning
• Using extra space despite requirement
• Incorrectly separating the cloned list