复杂链表的构成与复制
复杂链表的构成与复制
复杂链表的复制。一个链表的每个节点,有一个指向next指针指向下一个节点,还有一个random指针指向这个链表中的一个随机节点或者NULL,现在要求实现复制这个链表,返回复制后的新链表。
复杂链表的结构
typedef struct ComplexNode{
DataType _data ; // 数据
struct ComplexNode * _next; // 指向下一个节点的指针
struct ComplexNode * _random; // 指向随机节点(可以是链表中的任意节点 or 空)
}CNode;
先考虑如何生成一个复杂链表
从复杂链表的节点结构可以看出,该节点中药包含两个指针,一个指向下一个节点,一个指向任意节点或空,所以必须在创建链表时来给出节点的任意指针的指向
复杂链表的节点生成
生成复杂链表
打印复杂链表
测试用例
运行结果
该结构如下
复制复杂链表
方法1:第一步复制链表上的每个节点,并用_next指针将链表节点连接起来
第二步设置新链表上每个节点的_random指针的指向
对于一个含有n个节点的链表来说,因为每个链表的_random指向都必须从第一个节点开始查找,所以这种方法的时间复杂度为O(n*n)
方法2:借助哈希表
第一步复制链表上的每个节点,并用_next指针将链表节点连接起来,并且将原节点与复制后的节点的配对信息放到哈希表中。
第二步设置新链表上每个节点的_random指针的指向
有了哈希表就可以用O(1)的时间根据S找到S',相当于用空间换时间。对于有n个节点的链表需要大小为O(n)的哈希表,即这种方法的时间复杂度为O(n)
方法3:第一步根据原始链表的每个节点N创建一个节点N',将节点N'连接在节点N的后面
第二步设置复制出来的节点的_random指针
第三步将复制后的链表和原来的链表分离开
此算法的时间复杂度就是O(n)
主要讲第三种方法的实现过程
第一步
调用此函数后的结构图变为
第二步
调用此函数后的结构图变为
第三步
调用这三个函数
测试用例
运行结果