algoadvance

Leetcode 138. Copy List with Random Pointer

Problem Statement:

A linked list is given where each node contains an additional random pointer which could point to any node in the list or null.

You need to make a deep copy of this list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointers of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to a node in the original list.

For example, if there are two nodes in the original list and their random pointers point to each other, then the same should be true for the deep copy.

Clarifying Questions:

  1. Can we assume that the input list is non-circular and finite?
    • Yes, the input list is finite and non-circular.
  2. What is the structure of the node?
    • The node is defined as follows: 
      class Node {
public:
    int val;
    Node* next;
    Node* random;
    Node(int _val) {
        val = _val;
        next = nullptr;
        random = nullptr;
    }
};
  3. What should be returned?
    • You should return the head of the deep copied list.

Strategy:

To create a deep copy of the list, we can use a three-step approach:

  1. Create Interwoven List: Insert the copy nodes right after their corresponding original nodes.
  2. Assign Random Pointers: Set the random pointers for the copied nodes.
  3. Restore Original List: Separate the original and deep-copied list.

Code:

// 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 a new node for each original node and insert it between the original node and its next node.
        Node* cur = head;
        while (cur) {
            Node* newNode = new Node(cur->val);
            newNode->next = cur->next;
            cur->next = newNode;
            cur = newNode->next;
        }
        
        // Step 2: Assign random pointers for the new nodes.
        cur = head;
        while (cur) {
            if (cur->random) {
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }
        
        // Step 3: Separate the original and deep-copied list.
        Node* newHead = head->next;
        cur = head;
        while (cur) {
            Node* temp = cur->next;
            cur->next = temp->next;
            if (temp->next) {
                temp->next = temp->next->next;
            }
            cur = cur->next;
        }
        
        return newHead;
    }
};

Time Complexity:

The time complexity of this solution is O(n), where n is the number of nodes in the original list. This is because we traverse the list multiple times but each step is linear.

Therefore, the overall time complexity is O(n).

Space Complexity:

The space complexity of this solution is O(1) additional space, not counting the space required for the new nodes. This is because we don’t use any extra data structures that grow with the size of the input list.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI