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

本系列文章为《剑指Offer》刷题笔记。

刷题平台：

思路

大部分人首先想到的可能是先复制复杂指针的label和next，然后再查找random并更新。查找random又分为两种，一种是每次都从头查找，时间复杂度为O(n^2)；另一种是空间换时间，复制label和next的同时建立一个hash表来存放新旧复杂指针的对应关系，所以后续只需一步就能找到random，算法时间复杂度为O(n)。

我们这里将复杂链表的复制过程分解为三个步骤。在写代码的时候我们每一步定义一个函数，这样每个函数完成一个功能，整个过程的逻辑也就非常清晰明了了。

我们这里采用三步：

• 第一步：复制复杂指针的label和next。但是这次我们把复制的结点跟在元结点后面，而不是直接创建新的链表；
• 第二步：设置复制出来的结点的random。因为新旧结点是前后对应关系，所以也是一步就能找到random；
• 第三步：拆分链表。得到两个链表

代码详解图

# -*- coding:utf-8 -*-# class RandomListNode:#     def __init__(self, x):#         self.label = x#         self.next = None#         self.random = Noneclass Solution:    # 返回 RandomListNode    def Clone(self, pHead):        # write code here        if pHead == None:            return None        # 1.首先复制复杂指针的label和next，把复制的每个节点N，记为N'位于N的后面        pNode = pHead        while pNode:            pClone = RandomListNode(pNode.label)    # 申请新节点            pClone.next = pNode.next                # ①先连上            pNode.next = pClone                     # ②再断开            pNode = pClone.next                     # 重新开始一个pNode,插入新的复制节点                # 2.复制random随机指针        pNode = pHead          # pNode在刚才操作过程中已经移至链表尾部，需重置pNode。        while pNode:            pClone = pNode.next    # 先指向 A'，第二轮指向B'，以此类推            if pNode.random:                pClone.random = pNode.random.next            pNode = pClone.next                # 3.拆分链表  偶数位的节点即为我们要求的节点        # 申请一个新的链表（复制链表），其头结点为原链表头结点的下一个位置。        pCur, pCopy = pHead, pHead.next        while pCur:            pClone = pCur.next        # 克隆列表的第一个元素是A' -- 既是新链表的被删节点，也是克隆链表的一个节点            pCur.next = pClone.next                        if pCur.next:                pClone.next = pCur.next.next # 跳着取,这里第一次就取了B’                            pCur = pCur.next 	# 下一次操作的新指向，第一次取了B        return pCopy

Line 33:

pClone = pCur.next 这句很关键，我的理解是：既是新链表（第1步结束得到的全链表）的被删节点，也是克隆链表的一个节点

参考

https://cuijiahua.com/blog/2017/12/basis_25.html

https://blog.csdn.net/qq_41562704/article/details/89478626?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-5.not_use_machine_learn_pai&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-5.not_use_machine_learn_pai

https://blog.csdn.net/qq_43676757/article/details/106253305?utm_medium=distribute.pc_relevant.none-task-blog-title-2&spm=1001.2101.3001.4242