头像

飞鸟


访客:40

离线:16小时前



飞鸟
7天前

方法1 空间换时间

利用一个哈希表来记录原节点与复制节点之间的映射关系,根据映射关系修改复制节点的指针域

  1. 遍历链表,创建复制节点,同时将原节点与复制节点的映射加入到哈希表中

  2. 再次遍历链表,根据映射关系修改复制节点的指针域


class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        // 原节点与复制节点之间的映射
        unordered_map<ListNode*, ListNode*> hash;
        auto p = head;
        while(p)
        {
            auto node = new ListNode(p->val);
            hash[p] = node;
            p = p->next;
        }

        // modify pointer
        p = head;
        while(p)
        {
            hash[p]->next = hash[p->next];
            hash[p]->random = hash[p->random];
            p = p->next;
        }
        return hash[head];
    }
};

方法2 不使用辅助额外空间

  1. 遍历链表的同时,创建复制节点,并将节点添加到原节点的尾部

  2. 再次遍历链表,修改复制节点的random指针域

  3. 再次遍历链表,修改复制节点的next指针域,同时恢复原节点的next指针域

class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        if(!head)   return nullptr;
        auto p = head;
        // copy
        while(p)
        {
            auto node = new ListNode(p->val);
            node->next = p->next;
            p->next = node;
            p = node->next;
        }

        auto newHead = head->next;

        // modify random
        p = head;
        while(p)
        {
            auto node = p->next;
            node->random = p->random ? p->random->next : nullptr;
            p = node->next;
        }

        // modify next
        p = head;
        while(p)
        {
            auto node = p->next;
            p->next = node->next;
            node->next = p->next ? p->next->next : nullptr;
            p = p->next;
        }
        return newHead;
    }
};





飞鸟
7天前

按照上一题使用的层序遍历,只是奇数层和偶数层向level中放入的顺序不一样

  • 奇数层 从左到右

  • 偶数层 从右到左

其他完全一样

class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        if(!root)   return {};
        vector<vector<int>> res;
        queue<TreeNode*> q;
        q.push(root);
        bool from_left_to_right = true;

        while(q.size())
        {
            int n = q.size();
            vector<int> level(n);
            for(int i = 0; i < n; ++i)
            {
                auto node = q.front();
                q.pop();
                level[from_left_to_right ? i : n-1-i] = node->val;  // 放入顺序不一样
                if(node->left)  q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res.push_back(level);
            from_left_to_right = !from_left_to_right;
        }
        return res;
    }
};