剑指offer26复杂链表的复制

xiaoxiao2021-02-28  12

1.问题描述

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

2.思路解析

如果用哈希表存储pnode和pClonenode的映射关系,需要辅助空间O(n)。采用以下方法不需要额外空间,时间复杂度还相同。

此法分三步:

(1)复制结点

(2)复制特殊指针

(3)拆分链表

3.python代码

# -*- 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 pHead==None: return None p = pHead while p!=None: pClone = RandomListNode(p.label) pClone.next = p.next p.next = pClone p = pClone.next p = pHead while p!=None: pClone = p.next pClone.random = p.random.next if p.random!=None else None p = p.next.next pCloneHead = pHead.next p = pHead pClone = pCloneHead while pClone.next!=None: p.next = pClone.next p = pClone.next pClone.next = p.next pClone = p.next p.next = None return pCloneHead
转载请注明原文地址: https://www.6miu.com/read-2800296.html

最新回复(0)