138.Copy List with Random Pointer

Tags: Medium Linked List

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

---

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.

Example 1:

Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

1. You must return the copy of the given head as a reference to the cloned list.

---

/*
// 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) return head;
        if(m.find(head) == m.end()) {
            m[head] = new Node(head -> val);
            m[head] -> next = copyRandomList(head -> next);
            m[head] -> random = copyRandomList(head -> random);
        } 
        return m[head];
    }

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

递归解法。

考察点是深拷贝，通常我们定义一个新指针，区别是指针的值不同，但是指向的内存区域是相同的，这意味着如果指向的这块内存区域改变，则指针指向的对象也随之改变。深拷贝意味着指针指向的内存区域不同，但是内存区域存储的对象值相同，本题即对应节点存储的val，random指针指向的值，next指向的对象都相同，但是改变其中。

非递归解法：

/*
// 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) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (!head) return NULL;

        unordered_map<Node *, Node *> um;
        Node *dummy = new Node(-1);
        Node *p = dummy;
        Node *res = head; //保留head，二次遍历时使用
        //除了random部分的复制
        while (head) {
            Node *tmp = new Node(head -> val);
            p -> next = tmp;
            p = p -> next;
            um[head] = tmp;
            head = head -> next;
        }

        head = res;
        p = dummy -> next;
        while (head) {
            p -> random = um[head -> random];
            head = head -> next;
            p = p -> next;
        }

        return dummy -> next;
    }
};

---

如果题目要求变得严格一点，时间复杂度$O(n)$，空间复杂度为常数。

1. 在原链表的每个节点后面拷贝出一个新的节点。

2. 依次给新的节点的随机指针赋值，而且这个赋值非常容易 cur->next->random = cur->random->next。

3. 断开链表可得到深度拷贝后的新链表。

比如原链表是 1(2) -> 2(3) -> 3(1)，括号中是其 random 指针指向的结点，那么这个解法是首先比遍历一遍原链表，在每个结点后拷贝一个同样的结点，但是拷贝结点的 random 指针仍为空，则原链表变为 1(2) -> 1(null) -> 2(3) -> 2(null) -> 3(1) -> 3(null)。然后第二次遍历，是将拷贝结点的 random 指针赋上正确的值，则原链表变为 1(2) -> 1(2) -> 2(3) -> 2(3) -> 3(1) -> 3(1)，注意赋值语句为：

cur->next->random = cur->random->next;

这里的 cur 是原链表中结点，cur->next 则为拷贝链表的结点，cur->next->random 则为拷贝链表的 random 指针。cur->random 为原链表结点的 random 指针指向的结点，因为其指向的还是原链表的结点，所以我们要再加个 next，才能指向拷贝链表的结点。最后再遍历一次，就是要把原链表和拷贝链表断开即可

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        Node *cur = head;
        while (cur) {
            Node *t = new Node(cur->val, nullptr, nullptr);
            t->next = cur->next;
            cur->next = t;
            cur = t->next;
        }
        cur = head;
        while (cur) {
            if (cur->random) cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        cur = head;
        Node *res = head->next;
        while (cur) {
            Node *t = cur->next;
            cur->next = t->next;
            if (t->next) t->next = t->next->next;
            cur = cur->next;
        }
        return res;
    }
};

很显然此方法需要遍历三次链表，速度较上一种肯定较慢。