复杂链表的复制(注意深拷贝和浅拷贝的区别)(特殊的双向链表)

题目描述

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

题意分析：

题目里面说明，不要返回结点的引用，如果这样做了会返回为空。其实说的就是浅拷贝

深拷贝和浅拷贝的区别如下？？

简单的来说就是，在有指针的情况下，浅拷贝只是增加了一个指针指向已经存在的内存，而深拷贝就是增加一个指针并且申请一个新的内存，使这个增加的指针指向这个新的内存，采用深拷贝的情况下，释放内存的时候就不会出现在浅拷贝时重复释放同一内存的错误！

所以，对于本问题，采用深拷贝可以解决，代码如下：

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here、
        from copy import deepcopy
        return deepcopy(pHead)

方法二：使用循环来实现

通过修改指针的引用，从而达到修改链表的目的

两次遍历pHead链表，第一次修改next指针的指向，第二次修改random指针的指向，通过这两次修改，可以达到链表复制的目的。

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here、
        if not pHead:
            return None

        p = RandomListNode(pHead.label)
        # p链表的两个引用
        next_p = p
        random_p = p

        # pHead链表的引用
        random_pHead = pHead

        # 遍历 pHead 链表，来修改 next_p 链表指向的值
        while pHead.next:
            next_p.next = RandomListNode(pHead.next.label)
            pHead = pHead.next
            next_p = next_p.next

        # 遍历 random_pHead 链表，用它的值来修改 random_p 链表
        while random_pHead.next:
            if random_pHead.random: # random 结点的指向不能为空
                random_p.random = RandomListNode(random_pHead.random.label)
            random_pHead = random_pHead.next
            random_p = random_p.next

        # 修改 next_p 和 random_p 就能到达修改 p 链表的目的，因为前面两个都是对 p 链表的引用
        return p