Clone Linked List with Random Pointer in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Cloning a Simple Linked List with Random Pointers

What is the printed output of the cloned linked list's values and their random pointers after running the given clone function on a 3-node list?

DSA C

struct Node {
    int val;
    struct Node* next;
    struct Node* random;
};

// Assume cloneList function correctly clones the list
// Original list setup:
// Node1(val=1) -> Node2(val=2) -> Node3(val=3) -> NULL
// Random pointers: Node1.random = Node3, Node2.random = Node1, Node3.random = Node2

// After cloning, print cloned list as: val(random_val) -> ...

void printList(struct Node* head) {
    while (head) {
        printf("%d(%d) -> ", head->val, head->random ? head->random->val : -1);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    // Setup original list and clone it
    // Then print cloned list
}

A 1(1) -> 2(2) -> 3(3) -> NULL

B 1(3) -> 2(1) -> 3(2) -> NULL

C 1(-1) -> 2(-1) -> 3(-1) -> NULL

D 1(2) -> 2(3) -> 3(1) -> NULL

💡 Hint

Trace the random pointers carefully after cloning.

The clone should preserve the original random pointer connections. Node1's random points to Node3, so cloned Node1's random points to cloned Node3, and so on.

🧠 Conceptual

intermediate

Understanding the Purpose of Interleaving Nodes in Cloning

Why do we interleave cloned nodes between original nodes in the common cloning algorithm for a linked list with random pointers?

A To remove duplicate nodes from the list

B To sort the list nodes by their values

C To easily assign random pointers of cloned nodes without extra space

D To reverse the linked list in place

💡 Hint

Think about how random pointers are assigned without using a hash map.

Interleaving cloned nodes allows us to find the clone of any original node's random pointer by just looking at the next node, avoiding extra memory.

🔧 Debug

advanced

Identify the Bug in Cloning Random Pointers

What error will occur when running this snippet that tries to assign random pointers in the cloned list? for (Node* curr = head; curr != NULL; curr = curr->next->next) { if (curr->random != NULL) { curr->next->random = curr->random->next; } }

DSA C

for (Node* curr = head; curr != NULL; curr = curr->next->next) {
    if (curr->random != NULL) {
        curr->next->random = curr->random->next;
    }
}

A Segmentation fault due to curr->next being NULL

B No error, code runs correctly

C Compilation error: 'random' is not a member of Node

D Infinite loop due to incorrect loop condition

💡 Hint

Check if curr->next can be NULL inside the loop.

If curr is the last node, curr->next is NULL, so curr->next->random causes a segmentation fault.

❓ Predict Output

advanced

Output After Separating Cloned List from Interleaved List

Given an interleaved list of original and cloned nodes, what is the output of printing the cloned list values after separation?

DSA C

struct Node {
    int val;
    struct Node* next;
    struct Node* random;
};

// Interleaved list: 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> NULL
// After separation, print cloned list values:
void printCloned(struct Node* head) {
    struct Node* curr = head;
    while (curr) {
        printf("%d -> ", curr->val);
        curr = curr->next;
    }
    printf("NULL\n");
}

int main() {
    // Assume separation done correctly
    // head points to cloned list head
    printCloned(head);
}

A 3 -> 2 -> 1 -> NULL

B 1 -> 1 -> 2 -> 2 -> 3 -> 3 -> NULL

C NULL

D 1 -> 2 -> 3 -> NULL

💡 Hint

The cloned list contains only cloned nodes after separation.

After separation, cloned list contains only cloned nodes with values 1, 2, 3 in order.

🧠 Conceptual

expert

Time Complexity of Cloning a Linked List with Random Pointer

What is the overall time complexity of cloning a linked list with random pointers using the interleaving method?

A O(n), where n is the number of nodes

B O(n^2), due to nested loops

C O(1), constant time

D O(log n), because of binary search

💡 Hint

Consider how many times each node is visited.

The algorithm visits each node a constant number of times, so time complexity is linear O(n).

Practice

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

easy

A. Maintaining the correct random pointer connections in the cloned list

B. Copying the data values of each node

C. Reversing the linked list before cloning

D. Sorting the linked list nodes

Solution

1. Step 1: Understand the linked list structure

   A linked list with random pointers has two pointers per node: next and random. The random pointer can point to any node or null.

2. Step 2: Identify cloning challenge

   While copying nodes is straightforward, correctly assigning random pointers in the cloned list is tricky because random pointers may point to nodes not yet cloned.

3. Final Answer:

   Maintaining the correct random pointer connections in the cloned list -> Option A

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 are always null
• Copying only next pointers

2. Which of the following code snippets correctly creates a new node for cloning a linked list with random pointers in C?

easy

A. Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = oldNode->data; newNode->next = NULL; newNode->random = NULL;

B. Node newNode = malloc(sizeof(Node)); newNode.data = oldNode.data; newNode.next = NULL; newNode.random = NULL;

C. Node* newNode = malloc(Node); newNode->data = oldNode->data; newNode->next = NULL; newNode->random = NULL;

D. Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = oldNode->data; newNode->next = oldNode->next; newNode->random = oldNode->random;

Solution

1. Step 1: Check correct malloc usage

   In C, malloc requires sizeof(Node) to allocate memory. Casting to (Node*) is good practice.

2. Step 2: Verify initialization

   New node's data is copied, next and random pointers are set to NULL initially to avoid dangling pointers.

3. Final Answer:

   Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = oldNode->data; newNode->next = NULL; newNode->random = NULL; -> Option A

4. Quick Check:

   Correct malloc and initialization = Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = oldNode->data; newNode->next = NULL; newNode->random = NULL; [OK]

Hint: Use malloc with sizeof and initialize pointers to NULL [OK]

Common Mistakes:

• Missing sizeof in malloc
• Not casting malloc result
• Copying next and random pointers directly

3. Given the following linked list with random pointers:

Node1(data=1) -> Node2(data=2) -> NULL
Node1.random = Node2
Node2.random = Node2

What will be the random pointer of the cloned Node1 after cloning?

medium

A. Points to NULL

B. Points to cloned Node2

C. Points to original Node2

D. Points to cloned Node1

Solution

1. Step 1: Understand original random pointers

   Original Node1's random points to original Node2.

2. Step 2: Cloning preserves structure

   Cloned Node1's random should point to cloned Node2, not original nodes, to maintain independence.

3. Final Answer:

   Points to cloned Node2 -> Option B

4. Quick Check:

   Random pointer in clone = cloned target node [OK]

Hint: Random pointers in clone point to cloned nodes [OK]

Common Mistakes:

• Random pointer points to original node
• Random pointer set to NULL by mistake
• Confusing next and random pointers

4. Consider this buggy code snippet for cloning a linked list with random pointers:

while (curr != NULL) {
  Node* copy = (Node*)malloc(sizeof(Node));
  copy->data = curr->data;
  copy->next = curr->next;
  curr->next = copy;
  curr = curr->next;
}

What is the main error causing an infinite loop?

medium

A. Copy node's next pointer is not set to NULL

B. Updating curr to curr->next skips the newly inserted node

C. Not updating curr to curr->next->next after insertion

D. malloc size is incorrect

Solution

1. Step 1: Analyze pointer updates in loop

   After inserting copy node after curr, curr->next points to copy. Moving curr = curr->next moves to copy again.

2. Step 2: Identify infinite loop cause

   Loop never advances past copy node because curr is updated to copy, not original next node. It should be curr = curr->next->next.

3. Final Answer:

   Not updating curr to curr->next->next after insertion -> Option C

4. Quick Check:

   Advance curr by two nodes after insertion [OK]

Hint: Move curr two steps after inserting copy [OK]

Common Mistakes:

• Advancing curr by one node causes infinite loop
• Forgetting to link copy nodes properly
• Incorrect malloc size

5. You want to clone a linked list with random pointers in O(n) time and O(1) extra space. Which approach correctly achieves this?

hard

A. Reverse the original list, clone it, then reverse back

B. Use a hash map to store original to copy node mapping, then assign pointers

C. Copy nodes one by one and assign random pointers by searching original list each time

D. Create copy nodes interleaved with original nodes, set random pointers using original nodes, then separate lists

Solution

1. Step 1: Understand space and time constraints

   O(n) time and O(1) space means no extra data structures like hash maps.

2. Step 2: Use interleaving method

   Insert cloned nodes between original nodes, assign random pointers using original nodes, then detach cloned list. This avoids extra space.

3. Final Answer:

   Create copy nodes interleaved with original nodes, set random pointers using original nodes, then separate lists -> Option D

4. Quick Check:

   Interleaving nodes = O(1) space cloning [OK]

Hint: Interleave cloned nodes to avoid extra space [OK]

Common Mistakes:

• Using hash map increases space complexity
• Searching original list for random pointers is O(n^2)
• Reversing list does not help cloning random pointers