Copy List with Random Pointer

https://leetcode.com/problems/copy-list-with-random-pointer/description/

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

Return a deep copy of the list.

Thoughts

深度copy每个结点带有随机指针的列表，随机指针可指向列表中任意结点。深copy都是先建立起新节点和旧结点的一一映射，然后再去完善它们内部关系。Random pointer有一种很巧妙的解法，就是把复制出来的节点放在原节点旁(next)一一串起来。再重头遍历，每个节点的cp节点的random就是原节点random的next。再重头遍历，把cp节点依次串起来。

Code

/*
 * @lc app=leetcode id=138 lang=cpp
 *
 * [138] Copy List with Random Pointer
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;
        auto cur = head;
        while (cur != nullptr) {
            auto node = new Node(cur->val, cur->next, nullptr);
            cur->next = node;
            cur = node->next;
        } 
        cur = head;
        while (cur != nullptr) {
            auto node = cur->next;
            if (cur->random != nullptr) node->random = cur->random->next;
            cur = node->next;
        }
        auto new_head = head->next, new_cur = new_head;
        cur = head;
        while (cur != nullptr) {
            cur->next = new_cur->next;
            cur = cur->next;
            if (cur != nullptr) {
                new_cur->next = cur->next;
                new_cur = new_cur->next;
            }
        }
        return new_head;
    }
};
// @lc code=end

/*
 * @lc app=leetcode id=138 lang=cpp
 *
 * [138] Copy List with Random Pointer
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;
        unordered_map<Node*, Node*> m;
        auto cur = head;
        while (cur != nullptr) {
            m[cur] = new Node(cur->val, nullptr, nullptr);
            cur = cur->next;
        } 
        cur = head;
        while (cur != nullptr) {
            m[cur]->random = m[cur->random];
            m[cur]->next = m[cur->next];
            cur = cur->next;
        }
        return m[head];
    }
};
// @lc code=end

Analysis

TC: O(n), SC: O(n)

还有SC O(1)的解法：

把每个复制出来的结点和原结点紧挨着放在一个list里，这样找到原结点的random就能定位到新结点的random。