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

Time Complexity: Clone Linked List with Random Pointer

O(n)

Understanding Time Complexity

We want to understand how long it takes to copy a linked list where each node has a random pointer.

How does the time grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Clone linked list with random pointer
Node* cloneList(Node* head) {
    if (!head) return NULL;
    Node* curr = head;
    // Step 1: Insert cloned nodes
    while (curr) {
        Node* newNode = malloc(sizeof(Node));
        newNode->val = curr->val;
        newNode->next = curr->next;
        curr->next = newNode;
        curr = newNode->next;
    }
    // Step 2: Set random pointers
    curr = head;
    while (curr) {
        if (curr->random) curr->next->random = curr->random->next;
        curr = curr->next->next;
    }
    // Step 3: Separate lists
    curr = head;
    Node* cloneHead = head->next;
    Node* cloneCurr = cloneHead;
    while (curr) {
        curr->next = curr->next->next;
        if (cloneCurr->next) cloneCurr->next = cloneCurr->next->next;
        curr = curr->next;
        cloneCurr = cloneCurr->next;
    }
    return cloneHead;
}
    

This code creates a copy of each node, sets the random pointers for the copies, and then separates the original and cloned lists.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Three separate while loops each traversing the entire list once.
• How many times: Each loop runs once over all n nodes, so about 3n 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
100	About 300 steps
1000	About 3000 steps

Pattern observation: The operations grow linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to clone the list grows in a straight line as the list gets longer.

Common Mistake

[X] Wrong: "Because there are nested steps, the time must be quadratic O(n²)."

[OK] Correct: Each loop runs separately over the list, not inside each other, so the total work adds up linearly, not multiplies.

Interview Connect

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

Self-Check

"What if we used a hash map to store original-to-clone node mappings instead of inserting cloned nodes inline? How would the time complexity change?"