剑指Offer&＃xff08;二十五&＃xff09;&＃xff1a;复杂链表的复制

搜索微信公众号:&＃39;AI-ming3526&＃39;或者&＃39;计算机视觉这件小事&＃39; 获取更多算法、机器学习干货
csdn&＃xff1a;https://blog.csdn.net/baidu_31657889/
github&＃xff1a;https://github.com/aimi-cn/AILearners

一、引子

这个系列是我在牛客网上刷《剑指Offer》的刷题笔记&＃xff0c;旨在提升下自己的算法能力。
查看完整的剑指Offer算法题解析请点击CSDN链接&＃xff1a;剑指Offer完整习题解析
github地址&＃xff1a;https://github.com/aimi-cn/AILearners/tree/master/blog/Algorithm/jianzhi_offer

二、题目

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

1、思路

下图是一个含有 5 个结点的复杂链表。图中实线箭头表示 next 指针&＃xff0c;虚线箭头表示 random 指针。为简单起见&＃xff0c;指向 null 的指针没有画出。

第一步&＃xff1a;是根据原始链表的每个结点N 创建对应的 N’。把 N’链接在N的后面。图 1 的链表经过这一步之后的结构&＃xff0c;如图 2 所示。

第二步&＃xff1a;设置复制出来的结点的 random。假设原始链表上的 N 的 random 指向结点 S&＃xff0c;那么其对应复制出来的 N’是 N的 pext 指向的结点&＃xff0c;同样 S’也是 S 的 next 指向的结点。设置 random 之后的链表如下图3所示。

第三步&＃xff1a;把这个长链表拆分成两个链表。把奇数位置的结点用 next 链接起来就是原始链表&＃xff0c;把偶数位置的结点用 next 链接起来就是复制 出来的链表。图3中的链表拆分之后的两个链表下图4所示。

我们可以使用递归的方法实现~

2、编程实现

python

代码实现方案&＃xff1a;

# -*- coding:utf-8 -*-
# class RandomListNode:
# def __init__(self, x):
# self.label &＃61; x
# self.next &＃61; None
# self.random &＃61; None
class Solution:# 返回 RandomListNodedef Clone(self, pHead):# write code hereif not pHead:returnnewNode &＃61; RandomListNode(pHead.label)newNode.random &＃61; pHead.randomnewNode.next &＃61; self.Clone(pHead.next)return newNode

AIMI-CN AI学习交流群【1015286623】 获取更多AI资料

分享技术&＃xff0c;乐享生活&＃xff1a;我们的公众号计算机视觉这件小事每周推送“AI”系列资讯类文章&＃xff0c;欢迎您的关注&＃xff01;