Copying a Linked List with Random Pointers

This challenge focuses on creating a deep copy of a singly linked list where each node, in addition to a 'next' pointer, also has a 'random' pointer that can point to any node in the list (including itself or null). The goal is to produce a new linked list that is a complete copy, including the correct 'next' and 'random' pointers, without modifying the original list. This problem is useful in scenarios where you need to duplicate a complex data structure with arbitrary relationships between its elements.

Problem Description

You are given a singly linked list where each node has two pointers: next and random. The next pointer points to the next node in the list, and the random pointer can point to any node in the list (including itself, a previous node, or null). Your task is to write an algorithm to create a deep copy of this linked list.

The deep copy should have the following properties:

• New Nodes: The copied list should contain entirely new nodes, not just references to the original nodes.
• Correct next Pointers: The next pointer of each node in the copied list should point to the corresponding node in the copied list.
• Correct random Pointers: The random pointer of each node in the copied list should point to the corresponding node in the copied list. If the original node's random pointer was null, the copied node's random pointer should also be null.

Input: The head of the original linked list.

Output: The head of the deep copied linked list.

Edge Cases to Consider:

• Empty list (head is null).
• List with a single node.
• random pointers pointing to themselves.
• random pointers pointing to nodes that are not directly adjacent in the list.

Examples

Example 1:

Input: [1 -> 2 -> 3 -> 4]
        Random: 1 -> null -> 3 -> null

Output: [1' -> 2' -> 3' -> 4']
        Random: 1' -> null' -> 3' -> null'

Explanation: The copied list 1' -> 2' -> 3' -> 4' has the same structure and random pointers as the original list. 1' points to 2', 2' points to 3', 3' points to 4', and 1''s random pointer points to 3', while 2''s random pointer is null and 4''s random pointer is null.

Example 2:

Input: [7 -> 8 -> 10 -> 12]
        Random: null -> 8 -> null -> 12

Output: [7' -> 8' -> 10' -> 12']
        Random: null' -> 8' -> null' -> 12'

Explanation: The copied list 7' -> 8' -> 10' -> 12' mirrors the original. 7''s random pointer is null, 8''s random pointer points to 8', 10''s random pointer is null, and 12''s random pointer points to 12'.

Example 3: (Edge Case - Empty List)

Input: null
Output: null

Explanation: An empty list should return null.

Constraints

• The number of nodes in the linked list can range from 0 to 1000.
• The values of the nodes are not relevant to the problem; only the structure and pointers matter.
• The algorithm should ideally have a time complexity of O(n), where n is the number of nodes in the list.
• The algorithm should have a space complexity of O(n) due to the creation of new nodes.

Notes

A common approach is to first create a copy of each node and link them together using the next pointers. Then, iterate through the original list again, updating the random pointers of the copied nodes based on the random pointers of the original nodes. Consider using a hash map to store the mapping between original nodes and their corresponding copies to efficiently find the copied node when updating the random pointers. Remember to handle the null case for both next and random pointers correctly.