Copy List with Random Pointer II in C++ (O(n) Time, O(1) Space)

Note:

Your algorithm should run in O(n) time and use O(1) extra space.

Understanding the Problem

The core challenge of this problem is to create a deep copy of a linked list where each node has an additional random pointer. The deep copy should be a completely new list with no shared nodes with the original list. This problem is significant in scenarios where data structures need to be duplicated without affecting the original structure, such as in undo operations, cloning complex objects, etc.

Approach

To solve this problem, we can use a three-step approach:

1. Interweaving the original list with copied nodes: For each node in the original list, create a new node and insert it right after the original node. This way, the new nodes are interleaved with the original nodes.
2. Assigning random pointers: Iterate through the interleaved list and assign the random pointers for the new nodes.
3. Restoring the original list and extracting the copied list: Separate the interleaved list into the original list and the copied list.

Algorithm

Let's break down the algorithm step-by-step:

1. Iterate through the original list and create new nodes. Insert each new node right after its corresponding original node.
2. Iterate through the interleaved list and set the random pointers for the new nodes.
3. Separate the interleaved list into the original list and the copied list.

Code Implementation

// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = nullptr;
        random = nullptr;
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;

        // Step 1: Create new nodes and interleave them with original nodes
        Node* curr = head;
        while (curr) {
            Node* newNode = new Node(curr->val);
            newNode->next = curr->next;
            curr->next = newNode;
            curr = newNode->next;
        }

        // Step 2: Assign random pointers for the new nodes
        curr = head;
        while (curr) {
            if (curr->random) {
                curr->next->random = curr->random->next;
            }
            curr = curr->next->next;
        }

        // Step 3: Separate the interleaved list into original and copied lists
        Node* newHead = head->next;
        curr = head;
        while (curr) {
            Node* temp = curr->next;
            curr->next = temp->next;
            if (temp->next) {
                temp->next = temp->next->next;
            }
            curr = curr->next;
        }

        return newHead;
    }
};

Complexity Analysis

The time complexity of this approach is O(n) because we iterate through the list a constant number of times. The space complexity is O(1) extra space because we are not using any additional data structures that grow with the input size.

Edge Cases

Some potential edge cases include:

• An empty list (head is null).
• A list where all random pointers are null.
• A list where random pointers form a cycle.

Each of these cases is handled by the algorithm as it does not make any assumptions about the structure of the random pointers.

Testing

To test the solution comprehensively, consider the following test cases:

• Simple list with no random pointers.
• List with random pointers pointing to previous nodes.
• List with random pointers forming a cycle.
• Empty list.

Using a variety of test cases ensures that the solution handles all possible scenarios.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Break down the problem into smaller, manageable steps.
• Think about how to maintain the original structure while creating the new structure.
• Consider edge cases and how your solution handles them.
• Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to create a deep copy of a linked list with random pointers in C++. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in computer science.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode Problem: Copy List with Random Pointer
• Wikipedia: Deep Copy
• GeeksforGeeks: Clone a Linked List with Next and Random Pointer