本文共 1512 字，大约阅读时间需要 5 分钟。

题目

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

思路

拿到题的思路就是hash表+两次遍历，但看到书上有更能节省空间的办法后就直接写了书上的。

翻了个错误就是奇偶链表节点的处理上，还是不能拿个整数做%2操作来判断，需要指针处理，因为最后一个空节点不复制。

总的来说就是三个方法顺序操作一下。

代码

/*// 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) {        if(head == NULL){            return NULL;        }        copyList(head);        changeptr(head);        return GetNewList(head);    }    void copyList(Node* head){        Node* p = head;        while(p != NULL){            Node* pclone = new Node(p->val);            Node* p1 = p->next;            p->next = pclone;            pclone->next = p1;            p=pclone->next;        }    }    void changeptr(Node* head){        Node* p = head;                while(p != NULL){            Node* pnew = p->next;            if(p->random != NULL){                pnew->random = p->random->next;            }            p=pnew->next;        }    }    Node* GetNewList(Node* head){        Node* p = head;        Node* pnewhead = NULL;        Node* pnew = NULL;        pnewhead = p->next;        pnew = p->next;        p->next = pnewhead->next;        p = p->next;        while(p != NULL){            pnew->next = p->next;            pnew = p->next;            p->next = pnew->next;            p=p->next;        }        return pnewhead;    }};

转载地址：https://blog.csdn.net/hanmin822/article/details/105699205 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！