Leetcode.138.Copy List With Rand

题目

给定一个链表, 每个结点有两个指针, 一个指向next, 一个指向random.
对链表进行深拷贝.

class Node {
public:
    int val;
    Node* next;
    Node* random;
    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};

思路

unordered_map保存旧结点的和新节点的映射. 新链表的random先指向旧链表的random, 之后再使用map替换.

Node* copyRandomList(Node* head) {
    if (!head) return head;

    Node *res = new Node(head->val, nullptr, nullptr);
    res->random = head->random;
    Node *root = res;

    unordered_map<Node*, Node*> map;
    map[head] = res;
    while (head->next != nullptr) {
        Node *tmp = new Node(head->next->val, nullptr, nullptr);
        map[head->next] = tmp;
        tmp->random = head->next->random;
        res->next = tmp;
        res->random = head->random;
        res = res->next;
        head = head->next;
    }

    Node *tmp = root;
    while (tmp != nullptr) {
        tmp->random = map[tmp->random];
        tmp = tmp->next;
    }

    return root;
}

总结

链表的next和random双指针的时候, 需要仔细考虑每个指针的状态.