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

时间:2022-06-03 21:25:46

题目描述

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的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