Problem Statement

You are given a linked list where each node contains an additional random pointer. This pointer could point to any node in the list or be null.

Create a deep copy of this linked list. The deep copy should have n new nodes, where each new node's value matches the value of its corresponding node in the original list. Additionally, both the next and random pointers of the new nodes should point to the new nodes in the copied list.

The pointers in the copied list should maintain the same structure as the original list. None of the pointers in the new list should reference any node in the original list.

For instance, if in the original list, node X has a random pointer to node Y (X.random -> Y), then in the copied list, the corresponding nodes x and y should have a random pointer such that x.random -> y.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, randomIndex] where:

• val: It is an integer representing Node.val
• randomIndex: The index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Given a head of the linked list, return the head of the newly copied linked list.

Examples

Example 1:

• Input: head = [[3, 1], [4, null], [5, 0], [7, 2]]

• Output: [[3, 1], [4, null], [5, 0], [7, 2]]
• Explanation: The original list is cloned and returned.

Example 2:

• Input: head = [[1, 2], [2, 0], [3, 1]]

• Expected Output: [[1, 2], [2, 0], [3, 1]]
• Explanation: The original list is cloned and returned.

Example 3:

• Input: head = [[8, 2], [9, null], [7, 1]]

• Output: [[8, 2], [9, null], [7, 1]]
• Explanation: The original list is cloned and returned.

Constraints:

• 0 <= n <= 1000
• -10⁴ <= Node.val <= 10⁴
• Node.random is null or is pointing to some node in the linked list.

Solution

To solve this problem, we make three passes over the original linked list to create a deep copy that maintains the same next and random pointer structure as the original list. In the first pass, we insert a copy of each node right next to the original node. This helps us easily link the next pointers of the copied nodes. During the second pass, we set up the random pointers for the copied nodes using the established relationship between the original nodes and their copies. Finally, in the third pass, we separate the original and copied nodes, restoring the original list and forming the deep-copied list.

This approach is efficient because it only traverses the list three times, maintaining a linear time complexity of O(n). The algorithm avoids using extra space by cleverly utilizing the linked list structure to temporarily store the copied nodes next to their originals. This enables us to keep track of the next and random pointers without additional data structures, making the solution space-efficient with O(1) extra space.

Step-by-Step Algorithm

1. Check for Empty List:

   • If the input head is null, return null. This handles the edge case where the input list is empty.

2. First Pass: Create and Insert Copied Nodes:

   • Initialize a pointer current to the head of the original list.
   • Traverse the list while current is not null:
     • For each node (current), create a new node copy with the same value (current.val).
     • Set the next pointer of copy to current.next.
     • Insert copy right after current by setting current.next to copy.
     • Move current to copy.next (i.e., the next original node).

3. Second Pass: Set Random Pointers for Copied Nodes:

   • Reinitialize current to the head of the original list.
   • Traverse the list again while current is not null:
     • If current.random is not null, set the random pointer of current.next (the copied node) to current.random.next (the copy of the node current.random points to).
     • Move current to current.next.next (i.e., the next original node).

4. Third Pass: Separate the Original and Copied Lists:

   • Reinitialize current to the head of the original list.
   • Initialize copiedHead to head.next (the head of the copied list).
   • Use a pointer copy to iterate over the copied list, initially set to copiedHead.
   • Traverse the list while current is not null:
     • Set current.next to current.next.next to restore the original list.
     • If copy.next is not null, set copy.next to copy.next.next to form the copied list. This steps removes the node of the original list.
     • Move both current and copy to their respective next nodes.

5. Return the Head of the Copied List:

   • Return copiedHead, which points to the head of the deep-copied linked list.

Algorithm Walkthrough

Let's walk through the algorithm using the input head = [[3, 1], [4, null], [5, 0], [7, 2]].

• Input Linked List:
  • Node 1: Value 3, Random Pointer -> Node at index 1 (Node with value 4)
  • Node 2: Value 4, Random Pointer -> null
  • Node 3: Value 5, Random Pointer -> Node at index 0 (Node with value 3)
  • Node 4: Value 7, Random Pointer -> Node at index 2 (Node with value 5)

First Pass: Create and Insert Copied Nodes

1. Start with current at Node 1 (Value 3):

   • Create Node 1' (Value 3).
   • Insert Node 1' after Node 1:
     • The list becomes: 3 -> 3' -> 4 -> 5 -> 7.
   • Move current to Node 2 (Value 4).

2. At Node 2 (Value 4):

   • Create Node 2' (Value 4).
   • Insert Node 2' after Node 2:
     • The list becomes: 3 -> 3' -> 4 -> 4' -> 5 -> 7.
   • Move current to Node 3 (Value 5).

3. At Node 3 (Value 5):

   • Create Node 3' (Value 5).
   • Insert Node 3' after Node 3:
     • The list becomes: 3 -> 3' -> 4 -> 4' -> 5 -> 5' -> 7.
   • Move current to Node 4 (Value 7).

4. At Node 4 (Value 7):

   • Create Node 4' (Value 7).
   • Insert Node 4' after Node 4:
     • The list becomes: 3 -> 3' -> 4 -> 4' -> 5 -> 5' -> 7 -> 7'.
   • Move current to null, ending the first pass.

Second Pass: Set Random Pointers for Copied Nodes

1. Start with current at Node 1 (Value 3):

   • current.random points to Node 2 (Value 4).
   • Set Node 1'.random to Node 2'.random:
     • Node 3'.random is now correctly set to Node 2'.
   • Move current to Node 2 (Value 4).

2. At Node 2 (Value 4):

   • current.random is null.
   • Node 2'.random remains null.
   • Move current to Node 3 (Value 5).

3. At Node 3 (Value 5):

   • current.random points to Node 1 (Value 3).
   • Set Node 3'.random to Node 1'.random:
     • Node 3'.random is now correctly set to Node 1'.
   • Move current to Node 4 (Value 7).

4. At Node 4 (Value 7):

   • current.random points to Node 3 (Value 5).
   • Set Node 4'.random to Node 3'.random:
     • Node 4'.random is now correctly set to Node 3'.
   • Move current to null, ending the second pass.

Third Pass: Separate the Original and Copied Lists

1. Start with current at Node 1 (Value 3), copiedHead at Node 1' (Value 3), and copy at Node 1'.

   • Set current.next to Node 2 (restoring the original list).
   • Set copy.next to Node 2'.
   • Move current to Node 2 and copy to Node 2'.

2. At Node 2 (Value 4):

   • Set current.next to Node 3 (restoring the original list).
   • Set copy.next to Node 3'.
   • Move current to Node 3 and copy to Node 3'.

3. At Node 3 (Value 5):

   • Set current.next to Node 4 (restoring the original list).
   • Set copy.next to Node 4'.
   • Move current to Node 4 and copy to Node 4'.

4. At Node 4 (Value 7):

   • Set current.next to null (restoring the original list).
   • Set copy.next to null.
   • Move current to null and copy to null, ending the third pass.

Final Output

• Copied List:
  • 3' -> 4' -> 5' -> 7', with correct next and random pointers.
• Original List remains unchanged:
  • 3 -> 4 -> 5 -> 7.

Code

Complexity Analysis

Time Complexity

The time complexity of the solution is O(n), where n is the number of nodes in the linked list. This is because we perform three passes over the list:

• The first pass creates a copy of each node and inserts it immediately after the original node, taking O(n) time.
• The second pass sets the random pointers for the copied nodes, which also takes O(n) time.
• The third pass separates the original and copied lists, which again requires O(n) time. Thus, the total time complexity is O(n + n + n) = O(n).

Space Complexity

The space complexity is O(1) (excluding the space required for the output). This is because we do not use any extra space proportional to the input size; we only manipulate the existing nodes to achieve the deep copy.