牛客网 复杂链表的复制

题目:

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

解答:

思路参考:《苦练算法》-剑指Offer- 二十五、复杂链表的复制 -python编写

先复制原来链表

复制相互之间的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 pHead
        cloneNode=pHead
        # 复制链表
        while cloneNode:
            node=RandomListNode(cloneNode.label)
            node.next=cloneNode.next
            cloneNode.next=node
            cloneNode=node.next
        cloneNode=pHead
        # 复制相互之间的random指向
        while cloneNode:
            if cloneNode.random:
                cloneNode.next.random=cloneNode.random.next
            cloneNode=cloneNode.next.next
        cloneNode=pHead
        pHead=pHead.next
        # 将两个列表拆分
        while cloneNode.next:
            node=cloneNode.next
            cloneNode.next=node.next
            cloneNode=node
        return pHead

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏逸鹏说道

重温数据结构系列随笔:单链表(c#模拟实现)

上一节我们讲述了数据结构的基本概念,这一节让我们来讨论下单链表的概念和实现 我从书中简单摘录下单链表概念 ? 简单而言单链表的是通过许多节点构成,每个节点...

29150
来自专栏攻城狮的动态

[Objective-C Runtime] 成员变量与属性

34970
来自专栏菩提树下的杨过

Flash/Flex学习笔记(55):背面剔除与 3D 灯光

Animation in ActionScript3.0 这本书总算快学完了,今天继续:上一回Flash/Flex学习笔记(50):3D线条与填充 里,我们知道...

25480
来自专栏刘笑江的专栏

通过Swift学函数式编程

在文章SWIFT IS A LOT LIKE SCALA [1] 提到Swift和Scala有很大的相似之处,在某些特性甚至比Scala对函数式编程的支持更友好...

17350
来自专栏深度学习计算机视觉

java用内部类构造链表实现相关方法

代码 import com.sun.corba.se.impl.orbutil.graph.Node; /** * Created by junyi.pc ...

29190
来自专栏深度学习与计算机视觉

算法-寻找两个链表的第一个公共结点

题目: 输入两个链表,找到他们的第一个公共结点,链表结点定义如下: struct ListNode { int value; ListNode *n...

21560
来自专栏Bingo的深度学习杂货店

Q119 Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle. For example, give...

37880
来自专栏xx_Cc的学习总结专栏

iOS底层原理总结 - 探寻Class的本质

36070
来自专栏Jacklin攻城狮

Objective-C Runtime:深入理解类与对象

常说Objective-C是一门动态语言,那么问题来了,这个动态表现在那些方面呢?

23540
来自专栏Nian糕的私人厨房

JavaScript Date对象

JavaScript 的时间是由世界标准时间(UTC)1970 年 1 月 1 日开始,用毫秒计时

8530

扫码关注云+社区

领取腾讯云代金券