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