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

Time Complexity: Clone Linked List with Random Pointer

O(n)

Understanding Time Complexity

When cloning a linked list with random pointers, we want to know how the time needed grows as the list gets longer.

We ask: 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.

class Node:
    def __init__(self, val, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def clone_linked_list(head):
    if not head:
        return None
    
    # Step 1: Insert cloned nodes
    curr = head
    while curr:
        new_node = Node(curr.val, curr.next)
        curr.next = new_node
        curr = new_node.next
    
    # Step 2: Assign random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next
    
    # Step 3: Separate the lists
    curr = head
    clone_head = head.next
    while curr:
        clone = curr.next
        curr.next = clone.next
        if clone.next:
            clone.next = clone.next.next
        curr = curr.next
    
    return clone_head
    

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 each traverse the entire list once.
• How many times: Each loop runs approximately n times, where n is the number of nodes.

How Execution Grows With Input

Each loop goes through all nodes once, so the total steps add up but grow linearly with the list size.

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

Pattern observation: The total work grows directly in proportion to 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 three loops, the time complexity is O(n³)."

[OK] Correct: The loops run 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 skill valued in many coding challenges.

Self-Check

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