题解 | #复杂链表的复制#

题目的主要信息：

• 一个复杂链表除了有指向后一个节点的指针，还有一个指针随机节点的指针
• 将该复杂链表拷贝，返回拷贝链表的头节点
• 拷贝链表必须创建新的节点

举一反三：

学习完本题的思路你可以解决如下题目：

JZ18. 删除链表的节点

JZ6. 从尾到头打印链表

JZ52. 两个链表的第一个公共节点

JZ23. 链表环的入口

JZ25. 合并两个有序链表

方法一：组合链表（推荐使用）

知识点：双指针

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。

思路：

正常链表的复制，从头到尾遍历链表，对于每个节点创建新的节点，赋值，并将其连接好就可以了。这道题的不同之处在于我们还要将随机指针连接好，我们创建节点的时候，有可能这个节点创建了，但是它的随机指针指向的节点没有创建，因此创建的时候只能连接指向后面的指针，无法连接随机指针。

等链表连接好了，再连接随机指针的话，我们又难以找到这个指针指向的位置，因为链表不支持随机访问。但是吧，我们待拷贝的链表可以通过随机指针访问节点，那么我们不如将拷贝后的每个节点插入到原始链表相应节点之后，这样连接random指针的时候，原始链表random指针后一个元素就是原始链表要找的随机节点，而该节点后一个就是它拷贝出来的新节点，这不就可以连上了嘛。

//跟随前一个连接random
if(cur.random == null)
    clone.random = null;
else
    //后一个节点才是拷贝的
    clone.random = cur.random.next;

这样等随机指针链表完成之后，再遍历链表，将其拆分按照奇偶序列拆分成两个链表：只需要每次越过相邻节点连接就可以了。

//cur.next必定不为空
cur.next = cur.next.next;
cur = cur.next;
//检查末尾节点
if(clone.next != null)
    clone.next = clone.next.next;
clone = clone.next;

具体做法：

• step 1：遍历链表，对每个节点新建一个拷贝节点，并插入到该节点之后。
• step 2：使用双指针再次遍历链表，两个指针每次都移动两步，一个指针遍历原始节点，一个指针遍历拷贝节点，拷贝节点的随机指针跟随原始节点，指向原始节点随机指针的下一位。
• step 3：再次使用双指针遍历链表，每次越过后一位相连，即拆分成两个链表。

图示：

Java实现代码：

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        //空节点直接返回
        if(pHead == null)
            return pHead;
        //添加一个头部节点
        RandomListNode cur = pHead;
        //遍历原始链表，开始复制
        while(cur != null){
            //拷贝节点
            RandomListNode clone = new RandomListNode(cur.label);
            //将新节点插入到被拷贝的节点后
            clone.next = cur.next;
            cur.next = clone;
            cur = clone.next;
        }
        cur = pHead;
        RandomListNode clone = pHead.next;
        RandomListNode res = pHead.next;
        //连接新链表的random节点
        while(cur != null){
            //跟随前一个连接random
            if(cur.random == null)
                clone.random = null;
            else
                //后一个节点才是拷贝的
                clone.random = cur.random.next;
            //cur.next必定不为空
            cur = cur.next.next;
            //检查末尾节点
            if(clone.next != null)
                clone = clone.next.next;
        }
        cur = pHead;
        clone = pHead.next;
        //拆分两个链表
        while(cur != null){
            //cur.next必定不为空
            cur.next = cur.next.next;
            cur = cur.next;
            //检查末尾节点
            if(clone.next != null)
                clone.next = clone.next.next;
            clone = clone.next;
        }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        //空节点直接返回
        if(pHead == NULL)
            return pHead;
        //添加一个头部节点
        RandomListNode *cur = pHead;
        //遍历原始链表，开始复制
        while(cur != NULL){
            //拷贝节点
            RandomListNode *clone = new RandomListNode(cur->label);
            //将新节点插入到被拷贝的节点后
            clone->next = cur->next;
            cur->next = clone;
            cur = clone->next;
        }
        cur = pHead;
        RandomListNode *clone = pHead->next;
        RandomListNode *res = pHead->next;
        //连接新链表的random节点
        while(cur != NULL){
            //跟随前一个连接random
            if(cur->random == NULL)
                clone->random = NULL;
            else
                //后一个节点才是拷贝的
                clone->random = cur->random->next;
            //cur->next必定不为空
            cur = cur->next->next;
            //检查末尾节点
            if(clone->next != NULL)
                clone = clone->next->next;
        }
        cur = pHead;
        clone = pHead->next;
        //拆分两个链表
        while(cur != NULL){
            //cur->next必定不为空
            cur->next = cur->next->next;
            cur = cur->next;
            //检查末尾节点
            if(clone->next != NULL)
                clone->next = clone->next->next;
            clone = clone->next;
        }
        return res;
    }
};

Python实现代码：

class Solution:
    def Clone(self, pHead):
        #空节点直接返回
        if pHead is None:
            return pHead
        #添加一个头部节点
        cur = pHead
        #遍历原始链表，开始复制
        while cur is not None:
            #拷贝节点
            clone = RandomListNode(cur.label)
            #将新节点插入到被拷贝的节点后
            clone.next = cur.next
            cur.next = clone
            cur = clone.next
        cur = pHead
        clone = pHead.next
        res = pHead.next
        #连接新链表的random节点
        while cur is not None:
            #跟随前一个连接random
            if cur.random is None:
                clone.random = None
            else:
                #后一个节点才是拷贝的
                clone.random = cur.random.next
            #cur.next必定不为空
            cur = cur.next.next
            #检查末尾节点
            if clone.next is not None:
                clone = clone.next.next
        cur = pHead
        clone = pHead.next
        #拆分两个链表
        while cur is not None:
            #cur.next必定不为空
            cur.next = cur.next.next
            cur = cur.next
            #检查末尾节点
            if clone.next is not None:
                clone.next = clone.next.next
            clone = clone.next
        return res

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为链表长度，遍历三次链表，第一次遍历$nn$个节点，第二次、第三次遍历$2n2n$个节点
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间

方法二：哈希表（扩展思路）

知识点：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在$O(1)O(1)$时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

同样的，我们正常拷贝链表节点，只要能够保证我们可以随机访问就行了。因此我们可以考虑哈希表，利用哈希表对链表原始节点和拷贝节点之间建立映射关系，因此原始链表支持随机指针访问，这样我们建立映射以后，可以借助哈希表与原始链表的随机指针，在拷贝链表上随机访问。

具体做法：

• step 1：建立哈希表，key为原始链表的节点，value为拷贝链表的节点。
• step 2：遍历原始链表，依次拷贝每个节点，并连接指向后一个的指针，同时将原始链表节点与拷贝链表节点之间的映射关系加入哈希表。
• step 3：遍历哈希表，对于每个映射，拷贝节点的ramdom指针就指向哈希表中原始链表的random指针。

Java实现代码：

import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        //空节点直接返回
        if(pHead == null)
            return pHead;
        //添加一个头部节点
        RandomListNode res = new RandomListNode(0);
        //哈希表，key为原始链表的节点，value为拷贝链表的节点
        HashMap<RandomListNode, RandomListNode> mp = new HashMap<>();
        RandomListNode cur = pHead;
        RandomListNode pre = res;
        //遍历原始链表，开始复制
        while(cur != null){
            //拷贝节点
            RandomListNode clone = new RandomListNode(cur.label);
            //用哈希表记录该节点下的拷贝节点
            mp.put(cur, clone);
            //连接
            pre.next = clone;
            pre = pre.next;
            //遍历
            cur = cur.next;
        }
        //遍历哈希表
        for(HashMap.Entry<RandomListNode, RandomListNode> entry : mp.entrySet()){
            //原始链表中random为空
            if(entry.getKey().random == null)
                entry.getValue().random = null;
            else
                //将新链表的random指向哈希表中原始链表的random
                entry.getValue().random = mp.get(entry.getKey().random); 
        }
        //返回去掉头
        return res.next;
    }
}

C++实现代码：

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        //空节点直接返回
        if(pHead == NULL)
            return pHead;
        //添加一个头部节点
        RandomListNode *res = new RandomListNode(0);
        //哈希表，key为原始链表的节点，value为拷贝链表的节点
        unordered_map<RandomListNode*, RandomListNode*> mp;
        RandomListNode *cur = pHead;
        RandomListNode *pre = res;
        //遍历原始链表，开始复制
        while(cur != NULL){
            //拷贝节点
            RandomListNode *clone = new RandomListNode(cur->label);
            //用哈希表记录该节点下的拷贝节点
            mp[cur] = clone;
            //连接
            pre->next = clone;
            pre = pre->next;
            //遍历
            cur = cur->next;
        }
        //遍历哈希表
        for(auto node: mp){
            //原始链表中random为空
            if(node.first->random == NULL)
                node.second->random = NULL;
            else
                //将新链表的random指向哈希表中原始链表的random
                node.second->random = mp[node.first->random]; 
        }
        //返回去掉头
        return res->next;
    }
};

Python实现代码：

class Solution:
    def Clone(self, pHead):
        #空节点直接返回
        if pHead is None:
            return pHead
        #添加一个头部节点
        res = RandomListNode(0)
        #哈希表，key为原始链表的节点，value为拷贝链表的节点
        mp = dict()
        cur = pHead
        pre = res
        #遍历原始链表，开始复制
        while cur is not None:
            #拷贝节点
            clone = RandomListNode(cur.label)
            #用哈希表记录该节点下的拷贝节点
            mp[cur] = clone
            #连接
            pre.next = clone
            pre = pre.next
            #遍历
            cur = cur.next
        #遍历哈希表
        for (key, value) in mp.items():
            #原始链表中random为空
            if key.random is None:
                value.random = None
            else:
                #将新链表的random指向哈希表中原始链表的random
                value.random = mp[key.random] 
        #返回去掉头
        return res.next

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为链表的长度，遍历一次链表再遍历一次哈希表
• 空间复杂度：$O(n)O(n)$，哈希表的大小为链表长度