剑指Offer:复杂链表的复制

最新推荐文章于 2020-07-21 16:05:38 发布

destiny_python

最新推荐文章于 2020-07-21 16:05:38 发布

阅读量1.1k

点赞数

分类专栏： python 剑指offer 文章标签： python 链表

本文链接：https://blog.csdn.net/destiny_python/article/details/76114239

版权

python 同时被 2 个专栏收录

19 篇文章

订阅专栏

剑指offer

10 篇文章

订阅专栏

本文介绍了一种高效克隆复杂链表的方法，通过三个步骤实现：首先复制每个节点并插入到原节点之后；接着调整复制节点的随机指针指向；最后拆分链表得到完整的复制链表。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

# -*- coding:utf-8 -*-
#class RandomListNode:
#     def __init__(self, x):
#        self.label = x
#        self.next = None
#        self.random = None
"""
分三步：
第一步：复制每个节点，如：复制节点A得到A1，将A1插入节点A后面
第二步：遍历链表，A1->random = A->random->next;
第三步：将链表拆分成原链表和复制后的链表
"""
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        self.cloneNodes(pHead)
        self.ConnectSiblingNodes(pHead)
        return self.ReconnectNodes(pHead)
    #复制每个节点
    def cloneNodes(self, pHead):
        pNode = pHead
        while(pNode != None):
            #每次随机分配一个新地址来存放待赋值节点的值
            pCloned = RandomListNode(pNode.label)
            pCloned.next = pNode.next
            pCloned.random = None
            
            pNode.next = pCloned
            pNode = pCloned.next
            
    #遍历链表
    def ConnectSiblingNodes(self, pHead):
        pNode = pHead
        while(pNode != None):
            pCloned = pNode.next
            if (pNode.random != None):
                pCloned.random = pNode.random.next
            pNode = pCloned.next
    # 将链表拆分成原链表和复制后的链表
    def ReconnectNodes(self, pHead):
        pNode = pHead
        pClonedHead = None
        pClonedNode = None
        if (pNode != None):
            pClonedHead = pClonedNode = pNode.next
            pNode.next = pClonedNode.next
            pNode = pNode.next
            
        while(pNode != None):
            pClonedNode.next = pNode.next
            pClonedNode = pClonedNode.next
            pNode.next = pClonedNode.next
            pNode = pNode.next
        return pClonedHead