---
tags: leetcode
---

# [138. Copy List with Random Pointer](https://leetcode.com/problems/copy-list-with-random-pointer/)
---
# My Solution
## Solution 1
### The Key Idea for Solving This Coding Question
DFS and hash map
### C++ Code

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

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

        Node *copied = new Node(head->val);
        htbl[head] = copied;

        copied->next = copyRandomList(head->next);

        if (head->random != nullptr) {
            copied->random = htbl[head->random];
        }

        return copied;
    }

private:
    unordered_map<Node *, Node *> htbl;
};

### Time Complexity
$O(n)$
$n$ is the number of nodes in the linked list referred by `head`.
### Space Complexity
$O(n)$
## Solution 2
### The Key Idea for Solving This Coding Question
### C++ Code

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node *copyRandomList(Node *head) {
        if (head == nullptr) {
            return nullptr;
        }
        
        Node *it = head;
        while (it != nullptr) {
            Node *node = new Node(it->val);
            
            node->next = it->next;
            it->next = node;
            it = it->next->next;
        }
        
        Node *orgIt = head;
        while (orgIt != nullptr && orgIt->next != nullptr) {
            if (orgIt->random == nullptr) {
                orgIt = orgIt->next->next;
                continue;
            }
            
            Node *cloned = orgIt->next;
            cloned->random = orgIt->random->next;
            orgIt = orgIt->next->next;
        }
        
        Node *clonedHead = head->next, *clonedIt = clonedHead;
        orgIt = head;
        while (orgIt != nullptr && orgIt->next != nullptr) {
            orgIt->next = orgIt->next->next;
            orgIt = orgIt->next;
            
            if (orgIt == nullptr) {
                break;
            }
            clonedIt->next = clonedIt->next->next;
            clonedIt = clonedIt->next;
        }
        
        return clonedHead;
    }
};

### Time Complexity
$O(n)$
$n$ is the number of nodes in the linked list referred by `head`.
### Space Complexity
$O(1)$
# Miscellaneous
<!--
# Test Cases

[[7,null],[13,0],[11,4],[10,2],[1,0]]

[[1,1],[2,1]]

[[3,null],[3,0],[3,null]]

[]

* Wrong Answer

[[-1,null]]

-->