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