《剑指offer》面试题35:复杂链表的复制

马谦马谦马谦 数据结构和算法评论289字数 1100阅读3分40秒阅读模式

一、题目描述

请实现函数complex_list_node *clone_list(complex_list_node *head),复制一个复杂链表。在复杂链表中,每个节点除了有一个next指针指向下一个节点,还有一个random指针指向链表中的随机节点或nullptr。节点的C++定义如下:

如下是一个复杂链表示例,其中虚线是random指针:

《剑指offer》面试题35:复杂链表的复制-图片1

二、思路

复制过程可以分为三步,第一步,复制链表中的所有节点并插入到对应节点后,random指针和原节点指针保持一致:

《剑指offer》面试题35:复杂链表的复制-图片2

第二步,修改所有复制节点的random指针,修改成被复制出来的节点:

《剑指offer》面试题35:复杂链表的复制-图片3

第三步,把所有新复制出来的节点从原始链表中移除:

《剑指offer》面试题35:复杂链表的复制-图片4

三、代码实现

链表节点定义:

第一步克隆所有节点函数:

第二步修改random指针指向:

第三步分离原始链表和新克隆链表:

整合起来的复杂链表拷贝函数:

注意:这个函数里面一定要判断head是否为空的情况,前面三个函数因为是内部函数所以没有在入口判断head为空的情况!

四、单元测试

写代码容易,写单元测试麻烦,一个单元测试写了一小时。。。

4.1 链表创建函数

做单元测试,必不可少的一个测试函数是链表创建函数,因为要测试链表,首先要先创建链表:

测试这个函数的正确性:

4.1 测试功能

测试功能点:

  1. 空链表测试
  2. 非空链表测试
  3. 链表克隆后是否会影响原始链表

leetcode上也有这个一模一样的题目,下面的测试数据是基于leetcode来写的。

https://leetcode-cn.com/problems/copy-list-with-random-pointer/submissions/

TestFixtures定义:

测试克隆链表案例:

测试空链表复制:

测试是否修改了原链表:

测试结果:

《剑指offer》面试题35:复杂链表的复制-图片5

 
马谦马谦马谦
  • 本文由 马谦马谦马谦 发表于 2020年2月9日22:45:23
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/copy-list-with-random-pointer.html
redis源码分析:链表实现 Redis

redis源码分析:链表实现

一、链表定义 链表在redis中的使用十分广泛,例如列表的底层实现之一就是链表,包括发布、订阅等等功能都是有用到链表的。redis中链表在adlist.h和adlist.c中实现,只用了300+行代码...
匿名

发表评论

匿名网友
:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:
确定

拖动滑块以完成验证