Clone a linked list with next and random pointer

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.random = None
 
def clone_linked_list(head):
    # Create a hashmap to store the original node and its corresponding clone
    mapping = {}
 
    # Iterate through the original linked list and create a clone for each node
    current = head
    while current:
        mapping[current] = Node(current.data)
        current = current.next
 
    # Reset the current pointer to the head of the original linked list
    current = head
 
    # Iterate through the original linked list and connect the clone nodes with their corresponding pointers
    while current:
        clone = mapping[current]
        clone.next = mapping.get(current.next)
        clone.random = mapping.get(current.random)
        current = current.next
 
    # Return the head of the cloned linked list
    return mapping.get(head)
 
# Example usage:
# Create a linked list with next and random pointers
head = Node(1)
head.next = Node(2)
head.random = head.next
head.next.next = Node(3)
head.next.random = head
head.next.next.next = Node(4)
head.next.next.random = head.next
 
# Clone the linked list
cloned_head = clone_linked_list(head)
 
# Print the original linked list and the cloned linked list
current = head
while current:
    print(f"Original: {current.data} -> Next: {current.next.data if current.next else 'None'} -> Random: {current.random.data if current.random else 'None'}")
    current = current.next
 
current = cloned_head
while current:
    print(f"Cloned: {current.data} -> Next: {current.next.data if current.next else 'None'} -> Random: {current.random.data if current.random else 'None'}")
    current = current.next