It's our wits that make us men.

剑指offer(python)

Posted on By Xc L


python 剑指offer

python数据结构与算法 讲解牛客网剑指offer66题

斐波那契数列

题目描述 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。 n<=39

分析:斐波那契数列,形如:1、1、2、3、5、8、13…后一个数为前两位的和;

n num
n = 0 num = 0
n = 1 num = 1
n = 2 num = 1
n = 3 num = 2
…… ……
n = k f(k) = f(k-1)+f(k-2)
# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        ''' 递归做法,复杂度太大,2^n,算法复杂度过大不饿能通过测试
        # 但是逻辑实现上是没有问题的,也就是说用递归思路可以解决
        if n == 0:
            return 0
        if n == 1:
            return 1
        if n>1:
        	# f(n)=f(n-1)+f(n-2)
            num = self.Fibonacci(n-1)+self.Fibonacci(n-2)
            return num
        return None
        '''
        
        # 循环方式,时间复杂度n
        if n == 0:
            return 0
        if n == 1:
            return 1
        if n>1:
            a = 1
            b = 0
            ret = 0
            # 总结斐波那契数列的规律为,两个数a、b的和ret
            # 此时ret为这几个数中较大的数,然后令原来两个数中较大的a为b,然后,继续进行相加。依次类推。
            for i in range(0, n-1):
                ret = a + b
                # 将和作为较大数,另原来的较大数为较小数,再进行加和
                b = a
                a = ret
            return ret
        return None

解析: 斐波那契的递推公式:F[n]=F[n-1]+F[n-2](n>=3,F[1]=1,F[2]=1) image-20200323151817892

如果按照递归来写,时间复杂度随着n的变化:1,2,4,8,…2的n次方,这也就意味着当n较大的时候运算量很大,可能会出现运算超时、内存超出的现象。

循环的方式思路:求a、b的和,将a、b和作为新的较大数,另原来的较大数为新的较小数,再进行加和,依次类推。

跳台阶

题目描述 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

分析:很容易想到递归方式,第一次跳1个台阶,则剩下的跳法f(n-1);第一次跳2个台阶,则剩下的跳法f(n-2);所以总的跳法有f(n)=f(n-1)+f(n-2)。(n>=3)

另外,可以通过观察发现,跳台阶的过程就是斐波那契数列,

num台阶数 跳法总类 方式
num = 0 0 none
num = 1 1 1
num = 2 2 11、2
num = 3 3 111、12、21
num = 4 5 1111、112、121、211、22
…… …… ……

通过找规律发现,num = n时, f(n) = f(n-1)+f(n-2) (n>=3)

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        # n = 0 没有
        # n = 1 一种
        # n = 2 两种
        # n = 3 3种
        # n = 4 5种
        # 通过找规律发现f(n) = f(n-1)+f(n-2),当n>2的时候。满足Fabonacci,
        # n = 2, f(2) = 2
        # n = 1, f(1) = 1
        # 或者倒推:设一共有f(n)种跳法,
        # 从后往前,第一步跳1级台阶,剩下有f(n-1)种跳法;
        # 第一步跳2级台阶,剩下有f(n-2)种跳法;但是n必须大于等于3(即f(n-1)和f(n-2)存在
        if number < 1:
            return 0
        if number == 1:
            return 1
        if number == 2:
            return 2
        ret = 0
        a = 1
        b = 2
        for i in range(3, number+1):
            ret = a+b
            a = b
            b = ret
        return ret

image-20200323170355629

变态跳台阶

题目描述 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析:

num台阶数 跳法总类 方式
num = 0 0 none
num = 1 1 1
num = 2 2 11、2
num = 3 4 111、12、21、3
num = 4 8 1111、112、121、211、22、13、31、4
…… …… ……

num=n时,共有2^(n-1)跳法

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        # number = 0,没有
        # number = 1,1
        # number = 2,2
        # number = 3,4
        # number = 4,8种。
        # number = n,2^(n-1)
        # 因为f(n)=f(n-1)+f(n-2)+...+f(2)+f(1),
        # 有f(n-1)=f(n-2)+...+f(2)+f(1)
        # f(n) = 2*f(n-1)
        # ......
        # 其中f(1)=1,f(2)=2
        # 所以f(n)= 2^(n-1)
        if number == 1:
            return 1
        ret = 1
        a = 1
        for i in range(2, number+1):
            ret = 2 * a
            a = ret
        return ret
        # 或者直接一步:
        # return pow(2, number-1)

解析:第一次跳1个台阶,剩下f(n-1)跳法;第一次跳2个台阶,剩下f(n-2)跳法;……第一次跳n-2个台阶,剩下f(2)种跳法;第一次跳n-1个台阶,剩下f(1)种跳法。其中f(1)=1,f(2)=2。所以有f(n)=f(n-1)+f(n-2)+…+f(2)+f(1),有f(n-1)=f(n-2)+…+f(2)+f(1),所以 f(n) =f(n-1)+f(n-1)= 2 * f(n-1)。所以f(n)=2^(n-1),其中(n>1),f(1)=1。

丑数

题目描述 把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

分析:考点(数组)。

数组的概念,所谓数组,是有序的元素序列 。 若将有限个类型相同的变量的集合命名,那么这个名称为数组名。组成数组的各个变量称为数组的分量,也称为数组的元素,有时也称为下标变量。数组是在程序设计中,为了处理方便, 把具有相同类型的若干元素按无序的形式组织起来的一种形式。 这些无序排列的同类数据元素的集合称为数组。(索引值从0开始)在内存中连续的空间。

数组是长度固定的,列表是可变长度的,元组也是长度固定的,但是元组的元素值不可变,数组的元素值可变,列表元素值和长度都可以改变。

栈不同于数组,不可以随意访问,只可以访问栈顶,一次只能取一个。先进后出的结构。在python中也是用列表实现。追加用append()(其他语言是push()压入)、获取栈顶用list[-1]、弹出用pop()或delete() image-20200323213916280

队列:对于栈只可以从栈顶压入或弹出。对于队列来说,可以从一边添加,另一边取出。先入先出的结构,在python中队列也使用列表实现。添加使用insert()或append()、取出使用list[-1]、pop()。 image-20200323214449618

二维数组中的查找

题目描述 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        '''# 方法一:使用循环遍历查找;
        # 时间复杂度:O(m*n)
        for i in range(len(array)): # len(array)为二维数组行
            for j in range(len(array[0])): # len(array[0])二位数组的列
                if target == array[i][j]:
                    return True
        return False'''
        # 1 2 3 4
        # 3 4 5 6
        # 4 6 8 10
        # 9 11 13 14
        # 第二种:考虑右上角4,构成长方形,比较值的大小
        # 时间复杂度O(m+n)
        # 右上角array[i][j]的值为:value
        row_count = len(array) # 行
        i = 0
        column_count = len(array[0]) # 列
        j = len(array[0])-1
        while i<row_count and j>=0: 
            value = array[i][j] # 依次取每行的最后一个(每行中的最大值)
            if value == target:
                return True
            elif value>target:
                j -= 1 # 如果大了就在同一列减少一点
            else:
                i += 1 # 如果小了就取下一行的最后一位(该行的最大值)
                
        return False

解析:查找除了采用常规时间复杂度为m*n的遍历方法,还可以根据题目的提示进行灵活取值。

替换空格

题目描述 请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

分析:对于python字符串的替换,可以转换成列表list,直接遍历、替换列表元素的方式,使用.join()函数可以将列表转换成字符串。

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        s = list(s)
        count=len(s)
        for i in range(0,count):
            if s[i]==' ':
                s[i]='%20'
        return ''.join(s) # join()可以使列表转换成字符串

用两个栈实现队列

题目描述 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

分析:考虑栈和队列的取数据方式:栈是遵循“先入后出,后入先出”的原则,队列遵循“先入先出”的规则。

image-20200324092702220

# -*- coding:utf-8 -*-
class Solution:
    # 定义两个栈一个用于接收一个用于输出
    def __init__(self):
        # 定义一个栈用于接收
        self.acceptStack=[]
        # 定义一个栈用于输出
        self.outputStack=[]
    def push(self, node):
        # write code here
        # push操作就是在acceptStack上append
        self.acceptStack.append(node)
    def pop(self):
        # return xx
        # 判断是否为空(必须先判断是否为空)
        if self.outputStack == []:
        	# 如果outputStack为空就将从acceptStack中pop出的值添加到outputStack,直到acceptStack为空
            while self.acceptStack != []:
                self.outputStack.append(self.acceptStack.pop())
        
        if self.outputStack != []:
        	# 如果outputStack不为空,那么就可以直接对outputStack做pop操作
            return self.outputStack.pop()
        
        else:
        # 如果outputStack和acceptStack都为空,则返回None
            return None

旋转数组的最小数字

** 题目描述** 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

分析:可以使用遍历,复杂度为O(N);或者考虑二分查找法:

二分查找法:二分查找算法(英语:binary search algorithm),也称折半搜索算法(英语:half-interval search algorithm)、对数搜索算法(英语:logarithmic search algorithm),是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。二分查找算法在情况下的复杂度是对数时间,进行O(log n)次比较操作(n在此处是数组的元素数量,O是大O记号,log 是对数)。二分查找算法使用常数空间,无论对任何大小的输入数据,算法使用的空间都是一样的。除非输入数据数量很少,否则二分查找算法比线性搜索更快,但数组必须事先被排序。

image-20200326004739840

# 二分查找代码实现
# 有序的数组就用二分查找法
def bSearch(array, target):
    left = 0
    right = len(array) - 1
    while left <= right:
        mid = (left+right)//2  # mid = (left+right) >> 1 位运算,在底层语言中移位运算比除法速度快
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            left = mid + 1
        else:
            right = mid -1
            
     return None
        

解题代码:

# 由题意可以得出,|a[mid]-a[left]|<|a[mid|-a[right]|,则有left = mid
# 或者有 a[right]>a[mid],说明最小值在左边

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        # 判断数组是否为空
        if not rotateArray:
        	return 0
        left = 0
        right = len(rotateArray) - 1
        while left <= right:
        	mid = (left + right) >> 1
        	if rotateArray[mid] < rotateArray[mid - 1]:
        		# 比左边小
        		return rotateArray[mid]
        	elif rotateArray[mid] < rotateArray[right]:
        		right = mid - 1
        	else:
        		left = mid + 1
        return None

调整数组顺序使奇数位于偶数前面

题目描述 输入一个整数数组,实现一个函数来调整该数组中数字得顺序,使得所有得奇数位于数组得前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

分析:

方法一:新建一个空白列表用于存储计数值和偶数值,分别添加奇数项和偶数项。 方法二:考虑使用冒泡排序。

冒泡排序:它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。(时间复杂度 O(n²))

冒泡排序示意图

上图为冒泡排序示意图。需要遍历的数组长度每次减去1。

冒泡排序代码

def maopaoSort(array):
    # 一共需要n此的循环,每一个都要找到没排好序的最大值
    for i in range(len(array)):
        # 将 没有排好序的数组找最大值(没排好序的数组长度每次减少1),并一直将最大值放到最顶端
        for j in range(len(array) - i -1):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array


if __name__ == '__main__':
    array = [9, 8, 10, 15, 7, 3, 20, 14, 2]
    maopaoSort(array)
    print(array)

解题代码

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        # 第一种方法
        # 时间复杂的都O(n),空间复杂度O(n)
        ret = []
        # 先奇数添加
        for i in array:
             if i % 2 == 1:
                    ret.append(i)
        # 后添加偶数
        for i in array:
             if i % 2 == 0:
                    ret.append(i)
        return ret

包含min函数的栈

题目描述

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

注意:保证测试中不会当栈为空的时候,对栈调用pop()或者min()或者top()方法。

分析:

image-20200409005642016

解题代码

# -*- coding:utf-8 -*-
class Solution:
    # 定义一个栈
    def __init__(self):
        self.stack = []
        # 新建一个数组用来保存最小值数组
        self.minValue = []
    # Push和pop同时对两个数组操作
    def push(self, node):
        # write code here
        self.stack.append(node)
        if self.minValue:
            if self.minValue[-1] > node:
                self.minValue.append(node)
            else:
                self.minValue.append(self.minValue[-1])
        else:
            self.minValue.append(node)
    def pop(self):
        # write code here
        if self.stack == []:
            return None
        self.minValue.pop()
        return self.stack.pop()
    def top(self):
        # write code here
        if self.stack == []:
            return None
        return self.stack[-1]
    def min(self):
        # write code here
        if self.minValue == []:
            return None
        return self.minValue[-1]
    

栈的压入、弹出序列

题目描述

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序,假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

image-20200419005647874

分析:

首先按需要有一个栈(列表) 按照pushV的方式压入栈 弹出的时候需要循环判断是否需要弹出 判断需要弹出的情况的条件,压入栈的顶部和弹出栈的数据相等

解题代码

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        # 首先按需要有一个栈,列表
        # 按照pushV的方式压入栈
        # 弹出的时候需要循环判断是否需要弹出
        # 判断需要弹出的情况的条件,压入栈的顶部和弹出栈的数据相等
        if pushV == [] or len(pushV) != len(popV):
            return None
        stack = []
        index = 0
        for item in pushV:
            stack.append(item)
            # 循环判断是否弹出,以及stack是否为空
            while stack and stack[-1] == popV[index]:
                stack.pop()
                index += 1
            
        if stack == []:
            return True
        else:
            return False
        # return True if stack == [] else False

从头到尾打印链表

题目描述

输入一个链表,按链表从尾到头的顺序返回一个ArrayList。

分析:

链表定义 - 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

聊表可以存储非连续、非顺序、不定长度的数据 。指针位可以指向下一个元素的地址;链表的最后一个元素是None;链表分为:单链表、循环链表、双链表。python的

image-20200419005559437

image-20200419010215627

解题代码:

class Solution:
    # class ListNode:
    # def __init__(self, x):
        # self.val = x
        # self.next = None
    # 返回从尾部到头部的列表值序列,例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        
        ret = []
        pTmp = listNode
        while pTmp:
            # 使用insert(0)往0的索引位置添加元素
            ret.insert(0, pTmp.val)
            pTmp = pTmp.next
        return ret

链表中到数第k个结点

题目描述

输入一个链表,输出该链表中倒数第k个结点。

分析:

判断边界条件:如果k比链表长度大,直接返回None

如果k小于链表的长度,我们可以定义两个变量,这两个变量中间间隔k,一个存储长度为k的头部指针,一个存储为尾的指针。当k的值小于链表长度的时候,头部指针不为None的时候,头部指针依次取链表head的next,尾部指针也要取head的next,当头部指针firstPoint到达链表head的末尾的None的时候,这时的尾部指针secondPoint就是链表head中的倒数第k个结点;当k的值大于链表长度的时候,当头部指针依次增加到None的时候再next就会报错,这时要在头部指针firstPoint为None的时候集时返回None。

解题代码

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        # 判断边界条件:如果k比链表长度大,直接返回None
        # 如果k小于链表的长度,我们可以定义两个变量,这两个变量中间间隔k
        # 定义两个变量,一个存储长度为k的头部指针,一个存储为尾的指针
        # head为链表结构
        firstPoint = head
        secondPoint = head
        for i in range(k):
            # 先判断是否等于None
            if firstPoint == None:
                return None
            firstPoint = firstPoint.next
            
            
        while firstPoint != None:
            firstPoint = firstPoint.next
            secondPoint = secondPoint.next
        return secondPoint
        

反转链表

题目描述

输入一个链表,反转链表后,输出新链表的表头。

分析:将现有的头换成尾,尾部的next为空,从第二个node开始时,循环将next指向前一个

image-20200421143026685

解题代码

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        # 将现有的头换成尾,尾部的next为空,从第二个node开始时,循环将next指向前一个
        # 需要一直有一个指针指向还没有反转的链表的头部
        
        if pHead == None:
            # 空链表
            return None
        if pHead.next == None:
            # 只有一个结点的链表
            return pHead
        # 定义正向的链表中3个连续结点
        leftPointer = pHead
        midPointer = pHead.next
        rightPointer = midPointer.next
        # 定义反向特殊结点
        leftPointer.next = None
        
        while rightPointer != None:
            # 相当于依次取连续3个结点,直到结束rightPointer为空
            # 这时应该返回midPointer才是新链表的表头
            midPointer.next = leftPointer
            # midPointer成为新的leftPointer,在这里的原mid.next也成为left.next
            leftPointer = midPointer
            # rightPointer成为新的midPointer,在这里的原right.next也成为mid.next
            midPointer = rightPointer
            # 新rightPointer.next的指向为先前的rightPointer
            rightPointer = rightPointer.next
            
        # 这里为rightPointer为2个结点的的情况,交换前两个节点
        midPointer.next = leftPointer
        return midPointer

合并两个排序的链表

题目描述

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

分析:

情况分为:

1、当两个链表有一个为空的时候,直接返回另一个;

2、当链表不为空的时候,合并后的链表指针为原来排序的两个链表中的较小的那个,然后依次比较较小的next指针的val和较大的对应的val,取较小的那个作为合并链表的新指针。循环指导两个排序后的链表指向None,这时,将非空的那个链表添加到新的合并链表即可。

image-20200421212031651

解题代码

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1
        # 一个新的链表表头指针,取值为两个排序的链表表头中较小的一个
        newHead = pHead1 if pHead1.val < pHead2.val else pHead2
        # pHead1和pHeead2的临时指针
        pTmp1 = pHead1
        pTmp2 = pHead2
        if newHead == pHead1:
            # 如果pHead1为较小的一个,那么则指向pHead1的next为临时指针pTmp1
            pTmp1 = pHead1.next
        else:
            # 如果pHead2为较小的一个,那么则指向pHead2的next为临时指针pTm篇
            pTmp2 = pHead2.next
        # 一共四个指针,第四个为当前临时指针的前一个
        previousPointer = newHead
        
        # 当pTmp1和pTmp2都不为空的时候进行循环
        while pTmp2 and pTmp1:
            if pTmp1.val <= pTmp2.val:
                previousPointer.next = pTmp1
                # 向next方向取值
                previousPointer = pTmp1
                pTmp1 = pTmp1.next
            else:
                previousPointer.next = pTmp2
                previousPointer = pTmp2
                pTmp2 = pTmp2.next
        # 当pTmp1先变为空的时候,将剩余的pTmp2都放在后面排序
        if pTmp1 == None:
            previousPointer.next = pTmp2
        # 当pTmp2先变为空的时候,将剩余的pTmp1都放在后面排序
        else:
            previousPointer.next = pTmp1
        
        return newHead

复杂链表的复制

题目描述

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

分析:

1、边界条件 if pHead == None: return None

2、如果链表不为空:

如下图,复制一个node,实现复制体node的next指向,使原始链表头pTmp=pHead和node 同时指向pTmp.next,断开pTmp对于pTmp.next的指向,将pTmp指向复制体node,然后然后指定新的pTmp,pTmp = node.next。向后依次循环。

接下来实现复制体node的random的指向:因为pTmp.next.random = pTmp.random.next实现复制体node的random指向;向后移动两次pTmp = pTmp.next.next。

最后,断开原来的node和新的node之间的链接

image-20200422002827895

解题代码

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
# import copy
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # 方法一:深拷贝
        # ret = copy.deepcopy(pHead)  # 深拷贝可以
        # ret = copy.copy(pHead)  # 浅拷贝不行
        # 方法二:链表拷贝
        if pHead == None:
            return None
        # 以下是pHead非空的情况
        pTmp = pHead
        while pTmp:
            # 复制一个一样的node结点,并且添加到之前链表的每一个node后面
            node = RandomListNode(pTmp.label)
            # 指向同一个next
            node.next = pTmp.next
            # 断开前一个本体的pTmp结点指针指向复制体node
            pTmp.next = node
            # 指向下一个需要复制的结点node
            pTmp = node.next
        #########################################
        # A.next.random = a.random.next
        # 实现新建的node的random的指向
        pTmp = pHead
        while pTmp:
            if pTmp.random:
                # pTmp.random不为空的时候,为空的时候结束指向设定循环
                pTmp.next.random = pTmp.random.next
            pTmp = pTmp.next.next
        ########################################
        # 断开原来的node和新的node之间的链接
        pTmp = pHead
        newHead = pHead.next
        pNewTmp = pHead.next
        while pTmp:
            # print(pTmp.label)
            pTmp.next = pTmp.next.next
            if pNewTmp.next:
                pNewTmp.next = pNewTmp.next.next
                # 取下一个结点
                pNewTmp = pNewTmp.next
            # 取下一个结点
            pTmp = pTmp.next
        # 返回复制链表的head
        return newHead