Leetcode题解 剑指 Offer 35. 复杂链表的复制

PROBLEM

剑指 Offer 35. 复杂链表的复制

难度 中等

MY ANSWER

使用哈希表储存原链表节点与新链表节点的对应关系，根据表来构造新链表。时间复杂度空间复杂度都为O(n)。

/*
// 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:
    unordered_map<Node*, Node*> table;
    Node* copyRandomList(Node* head) {
        if(!head) {
            return nullptr;
        }
        Node* tmp = head;
        Node* dup = NULL;
        dup = new Node(tmp->val);
        table[tmp] = dup;
        tmp = tmp->next;
        Node* dhead = dup;
        while (tmp) {
            dup->next = new Node(tmp->val);
            dup = dup->next;
            table[tmp] = dup;
            tmp = tmp->next;
        }
        tmp = head;
        dup = dhead;
        while(dup) {
            if(tmp->random) {
                dup->random = table[tmp->random];
            }
            else {
                dup->random = NULL;
            }
            tmp = tmp->next;
            dup = dup->next;
        }
        return dhead;
    }
};

代码可以更简洁点，先遍历一次创建哈希表，再遍历一次把next、random都构造好。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        Node* cur = head;
        unordered_map<Node*, Node*> map;
        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != nullptr) {
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        // 4. 构建新链表的 next 和 random 指向
        while(cur != nullptr) {
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        // 5. 返回新链表的头节点
        return map[head];
    }
};

BETTER SOLUTION

构建 原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> …… 的拼接链表，根据拼接链表来设置random和next，时间复杂度相同，空间复杂度减少到O(1)。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        Node* cur = head;
        // 1. 复制各节点，并构建拼接链表
        while(cur != nullptr) {
            Node* tmp = new Node(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = tmp->next;
        }
        // 2. 构建各新节点的 random 指向
        cur = head;
        while(cur != nullptr) {
            if(cur->random != nullptr)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        // 3. 拆分两链表
        cur = head->next;
        Node* pre = head, *res = head->next;
        while(cur->next != nullptr) {
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = nullptr; // 单独处理原链表尾节点
        return res;      // 返回新链表头节点
    }
};

SUMMARY

使用拼接链表来降低空间复杂度。