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

题目的意思就是深拷贝复杂链表

错误解法：浅拷贝

解法1：哈希表

思想：

​ 将新节点和旧节点映射，新节点找到旧节点找到旧节点的next和random

复杂度：

​ ●时间：O(N)，遍历了两次链表

​ ●空间：O(N)，新建了unordered_map

代码：

class Solution {
   public:    Node* copyRandomList(Node* head) {
           if(head == NULL)            return NULL;        unordered_map
   
    map;        Node* ptr = head;        while(ptr != NULL){
            	//建立映射关系，旧节点映射到新节点            map[ptr] = new Node(ptr->val);            ptr = ptr->next;        }        ptr = head;        while(ptr != NULL){
               //新节点的next要是新节点，前后的map都要加            map[ptr]->next = map[ptr->next];            map[ptr]->random = map[ptr->random];            ptr = ptr->next;        }        return map[head];    }};
   

解法2：拼接 + 拆分

思想：

​ 1、2l两次遍历不能合并，因为要先构建拼接链表，才能访问新节点的random即cur->random->next

​

复杂度：

​ ●时间：O(N)，遍历3次链表

​ ●空间：O(1)

代码：

class Solution {
   public:    Node* copyRandomList(Node* head) {
           if(head == NULL)            return NULL;        Node* ptr = head;        //拼接链表        while(ptr != NULL){
               Node* new_node = new Node(ptr->val);            new_node->next = ptr->next;            ptr->next = new_node;            ptr = new_node->next;        }        ptr = head;        //不能与拼接合并        //这里的拼接链表长度一定为偶数，所以不需要判断ptr->next != NULL        while(ptr != NULL){
               if(ptr->random != NULL)                ptr->next->random = ptr->random->next;            ptr = ptr->next->next;        }        Node* old_ptr = head;        Node* new_ptr = head->next;        //把新节点的头保存起来        Node* new_head = head->next;        //不能用new_ptr != NULL，因为到了新链表最后一个节点，就不能访问next的next，所以访问到新链表的倒数第二个节点即new_ptr->next != NULL        while(new_ptr->next != NULL){
               old_ptr->next = old_ptr->next->next;            old_ptr = old_ptr->next;            new_ptr->next = new_ptr->next->next;            new_ptr = new_ptr->next;        }        //旧链表的最后一个节点的next设为NULL，不然还是指向它的复制，就修改了原链表        old_ptr->next = NULL;        return new_head;    }};