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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cloning a 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 code?

DSA Python

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

def print_list(head):
    result = []
    current = head
    while current:
        random_val = current.random.val if current.random else None
        result.append(f"{current.val}({random_val})")
        current = current.next
    print(' -> '.join(result) + ' -> None')

def clone_linked_list(head):
    if not head:
        return None

    # Step 1: Insert cloned nodes
    current = head
    while current:
        new_node = Node(current.val, current.next)
        current.next = new_node
        current = new_node.next

    # Step 2: Copy random pointers
    current = head
    while current:
        if current.random:
            current.next.random = current.random.next
        current = current.next.next

    # Step 3: Separate lists
    current = head
    clone_head = head.next
    while current:
        clone = current.next
        current.next = clone.next
        clone.next = clone.next.next if clone.next else None
        current = current.next

    return clone_head

# Create linked list: 1 -> 2 -> 3 -> None
node3 = Node(3)
node2 = Node(2, node3)
node1 = Node(1, node2)

# Setup random pointers
node1.random = node3
node2.random = node1
node3.random = node2

cloned_head = clone_linked_list(node1)
print_list(cloned_head)

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

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

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

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

💡 Hint

Focus on how random pointers are copied to the cloned nodes.

The cloned list nodes have the same values as original nodes. Their random pointers point to the clones of the original nodes' random targets. So node 1's clone random points to node 3's clone, node 2's clone random points to node 1's clone, and node 3's clone random points to node 2's clone.

🧠 Conceptual

intermediate

Understanding the purpose of interleaving cloned nodes

Why do we insert cloned nodes between original nodes in the linked list during cloning with random pointers?

A To reverse the linked list in place

B To sort the linked list nodes by value

C To remove duplicate nodes from the list

D To easily assign random pointers of cloned nodes using original nodes' random pointers

💡 Hint

Think about how the cloned node can find the clone of the random target without extra space.

By placing cloned nodes right after their originals, the clone of any node's random pointer target is just the next node of that target. This allows setting random pointers without extra memory.

🔧 Debug

advanced

Identify the error in this cloning step

What error will this code cause when cloning the random pointers? current = head while current: current.next.random = current.random.next current = current.next.next

A No error, code runs correctly

B SyntaxError due to missing colon

C AttributeError when current.random is None

D Infinite loop because current is never updated

💡 Hint

What if a node's random pointer is None?

If current.random is None, trying to access current.random.next causes AttributeError because None has no attribute 'next'.

❓ Predict Output

advanced

Output after separating cloned list

Given the interleaved list after cloning nodes, what is the output of printing the original list after separation?

DSA Python

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

def print_list(head):
    result = []
    current = head
    while current:
        random_val = current.random.val if current.random else None
        result.append(f"{current.val}({random_val})")
        current = current.next
    print(' -> '.join(result) + ' -> None')

# Original list: 1 -> 2 -> None
node2 = Node(2)
node1 = Node(1, node2)
node1.random = node2
node2.random = node2

# Interleaved list: 1 -> 1' -> 2 -> 2' -> None
node1_clone = Node(1)
node2_clone = Node(2)
node1.next = node1_clone
node1_clone.next = node2
node2.next = node2_clone
node2_clone.next = None

# Separate lists
current = node1
while current:
    clone = current.next
    current.next = clone.next
    clone.next = clone.next.next if clone.next else None
    current = current.next

print_list(node1)

A 1(2) -> 2(2) -> None

B 1(None) -> 2(None) -> None

C 1(1) -> 2(1) -> None

D 1(2) -> 2(None) -> None

💡 Hint

Check if original nodes' random pointers remain unchanged after separation.

The original nodes keep their original random pointers. Node 1's random points to node 2, node 2's random points to itself.

🚀 Application

expert

Minimum space complexity for cloning linked list with random pointer

What is the minimum extra space complexity to clone a linked list with random pointers without using a hash map or dictionary?

A O(n) - using a hash map to store original to clone mapping

B O(1) - constant extra space by interleaving cloned nodes

C O(log n) - using recursion stack for cloning

D O(n^2) - by nested loops to find random pointers

💡 Hint

Think about the interleaving technique that avoids extra data structures.

By inserting cloned nodes between original nodes, we can set random pointers without extra space, achieving O(1) extra space complexity.