06-22 01:44 阅读 53

leetcode 复制带随机指针的链表中等

完整题目链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

时间 O(n)，空间 O(1) 的做法参考：https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/fu-zhi-dai-sui-ji-zhi-zhen-de-lian-biao-c2nvs/

题目要求我们复制一个长度为 n 的链表，该链表除了每个节点有一个指针指向下一个节点外，还有一个额外的指针指向链表中的任意节点或者 null，如下图所示：

如何去复制一个带随机指针的链表？

首先我们可以忽略 random 指针，然后对原链表的每个节点进行复制，并追加到原节点的后面，而后复制 random 指针。最后我们把原链表和复制链表拆分出来，并将原链表复原。

图示过程如下：

1、在每个节点的后面加上它的复制，并将原链表和复制链表连在一起。

2、从前往后遍历每一个原链表节点，对于有 random 指针的节点 p，我们让它的 p->next->random = p->random->next，这样我们就完成了对原链表 random 指针的复刻。

3、最后我们把原链表和复制链表拆分出来，并将原链表复原。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node *ptr = head;
        while(ptr) {
            Node *copy = new Node(ptr -> val);
            Node *nxt = ptr -> next;
            ptr -> next = copy;
            copy -> next = nxt;
            ptr = nxt;
        }

        ptr = head;
        while(ptr) {
            if(ptr -> random) {
                ptr -> next -> random = ptr -> random -> next;
            }
            ptr = ptr -> next -> next;
        }

        Node *vHead = new Node(-1), *cur = vHead;
        ptr = head;
        while(ptr) {
            Node *nxt = ptr -> next;
            cur -> next = ptr -> next;
            ptr -> next = ptr -> next -> next;
            cur = nxt;
            ptr = ptr -> next;
        }

        auto ret = vHead -> next;
        delete vHead;
        return ret;
    }
};

时间 O(n)，空间 O(n) 的比较简单，将整个链表存进 vector，在来一个迭代器与下标的映射即可：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        while(head) {
            nodeList.push_back(head);
            copyNodeList.push_back(new Node(head -> val));
            ptrToIdx[head] = nodeList.size() - 1;
            head = head -> next;
        }

        for(int i = 0; i < copyNodeList.size(); ++ i) {
            if(i > 0) {
                copyNodeList[i - 1] -> next = copyNodeList[i];
            }
            if(ptrToIdx.find(nodeList[i] -> random) != ptrToIdx.end()) {
                copyNodeList[i] -> random = copyNodeList[ptrToIdx[nodeList[i] -> random]];
            }
        }
        return copyNodeList.empty() ? nullptr : copyNodeList.front();
    }

private:
    unordered_mapint> ptrToIdx;     // 链表指针与 vector 存放链表的下标映射关系
    vector nodeList;
    vector copyNodeList;
};

原文：https://www.cnblogs.com/rookie-acmer/p/15306825.html

leetcode 复制带随机指针的链表 中等

leetcode 复制带随机指针的链表中等