题目:有一个复杂链表,其结点除了有一个m_pNext指针指向下一个结点外,还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下:
struct ComplexNode
{
int m_nValue;
ComplexNode* m_pNext;
ComplexNode* m_pSibling;
};
下图是一个含有4个结点的该类型复杂链表。
请完成函数ComplexNode* Clone(ComplexNode* pHead),以复制一个复杂链表。
分析:在常见的数据结构上稍加变化,这是一种很新颖的面试题。要在不到一个小时的时间里解决这种类型的题目,我们需要较快的反应能力,对数据结构透彻的理解以及扎实的编程功底。
看到这个问题,我的第一反应是分成两步:第一步是复制原始链表上的每个链表,并用m_pNext链接起来。第二步,假设原始链表中的某节点N的m_pSibling指向结点S。由于S的位置在链表上有可能在N的前面也可能在N的后面,所以要定位N的位置我们需要从原始链表的头结点开始找。假设从原始链表的头结点开始经过s步找到结点S。那么在复制链表上结点N的m_pSibling的S’,离复制链表的头结点的距离也是s。用这种办法我们就能为复制链表上的每个结点设置m_pSibling了。
对一个含有n个结点的链表,由于定位每个结点的m_pSibling,都需要从链表头结点开始经过O(n)步才能找到,因此这种方法的总时间复杂度是O(n2)。
由于上述方法的时间主要花费在定位结点的m_pSibling上面,我们试着在这方面去做优化。我们还是分为两步:第一步仍然是复制原始链表上的每个结点N,并创建N’,然后把这些创建出来的结点链接起来。这里我们对<N,N’>的配对信息放到一个哈希表中。第二步还是设置复制链表上每个结点的m_pSibling。如果在原始链表中结点N的m_pSibling指向结点S,那么在复制链表中,对应的N’应该指向S’。由于有了哈希表,我们可以用O(1)的时间根据S找到S’。
第二种方法相当于用空间换时间,以O(n)的空间消耗实现了O(n)的时间效率。
接着我们来换一种思路,在不用辅助空间的情况下实现O(n)的时间效率。第三种方法的第一步仍然是根据原始链表的每个结点N,创建对应的N’。这一次,我们把新创建的每个结点N’链接在原先结点N的后面。代码如下:
/*
Clone all nodes in a complex linked list with head pHead,
and connect all nodes with m_pNext link
*/
void CloneNodes(ComplexNode* pHead)
{
ComplexNode* pNode = pHead;
while(pNode != NULL)
{
ComplexNode *pCloned = new ComplexNode();
pCloned->m_nValue = pNode->m_nValue;
pCloned->m_pNext = pNode->m_pNext;
pCloned->m_pSibling = NULL;
pNode->m_pNext = pCloned; //将新复制的结点链接在原始结点的后面
pNode = pCloned->m_pNext;
}
}
第二步是设置我们复制出来的链表上的结点的m_pSibling。假设原始链表上的N的m_pSibling指向结点S,那么其对应复制出来的N’是N->m_pNext,同样S’也是S->m_pNext。这就是我们在上一步中把每个结点复制出来的结点链接在原始结点后面的原因。有了这样的链接方式,我们就能在O(1)中就能找到每个结点的m_pSibling了。代码如下:
/*
Connect sibling nodes in a complex link list
*/
void ConnectSiblingNodes(ComplexNode* pHead)
{
ComplexNode* pNode = pHead;
while(pNode != NULL) //遍历链表更新随机指针
{
ComplexNode *pCloned = pNode->m_pNext;
if(pNode->m_pSibling != NULL)
{
pCloned->m_pSibling = pNode->m_pSibling->m_pNext; //新复制结点的随机指针就是原始结点的随机指针指向的结点的下一个结点
}
pNode = pCloned->m_pNext;
}
}
第三步是把这个长链表拆分成两个:把奇数位置的结点链接起来就是原始链表,把偶数位置的结点链接出来就是复制出来的链表。要实现这一步,也不是很难的事情。其对应的代码如下:
/*
Split a complex list into two:
Reconnect nodes to get the original list, and its cloned list
*/
ComplexNode* ReconnectNodes(ComplexNode* pHead)
{
ComplexNode* pNode = pHead;
ComplexNode* pClonedHead = NULL;
ComplexNode* pClonedNode = NULL;
if(pNode != NULL)
{
pClonedHead = pClonedNode = pNode->m_pNext;
pNode->m_pNext = pClonedNode->m_pNext;
pNode = pNode->m_pNext;
}
while(pNode != NULL)
{
pClonedNode->m_pNext = pNode->m_pNext; //把偶数位置的结点链接起来就是复制出来的新链表
pClonedNode = pClonedNode->m_pNext;
pNode->m_pNext = pClonedNode->m_pNext; //把奇数位置的结点链接起来就是原始链表
pNode = pNode->m_pNext;
}
return pClonedHead;
}
我们把上面三步合起来,就是复制链表的完整过程:
ComplexNode* Clone(ComplexNode* pHead)
{
CloneNodes( pHead );
ConnectSiblingNodes( pHead );
return ReconnectNodes( pHead );
}
转载自http://zhedahht.blog.163.com/
分享到:
相关推荐
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会...
python 实现 复杂链表的复制
今天我们要实现的就是对这样一个复杂链表复制产生一个新的复杂链表。 复杂链表的数据结构如下: typedef int DataType; //数据域的类型 //复杂链表的数据结构 typedef struct ComplexNode { DataType _data ; // ...
java基础面试题复杂链表的复制本资源系百度网盘分享地址
剑指 Offer 35. 复杂链表的复制标签:哈希表、链表难度:中等题目大意给定一个链表,每个节点除了 next 指针之后,还包含一个随机指针 random,该
示例 1:// Definition for a Node.Node* copyRandomList(Node* head) {//(1)拷贝数据struct
剑指 Offer 35. 复杂链表的复制python(csdn)————程序
1、遍历链表,复制每个结点,如复制结点A得到A1,将结点A1插到结点A后面 2、重新遍历链表,复制老结点的随机指针给新结点,如A1.random = A.ran
三步走:1. 首先克隆节点,接在原节点后面3. 把新链表和原链表拆出来RandomListNode* node=pHead;RandomListNode *cl
剑指Offer(Python多种思路实现):复杂链表的复制 面试35题: 题目:复杂链表的复制 题:输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为...
所以,我们需要在一开始把所有的节点都创建出来,避免 random 找不到指向,每个节点都对应着一个新的节点,原链表中的节点有 val、next、random 三
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
主要介绍了Java面试题-实现复杂链表的复制代码分享,小编觉得还是挺不错的,具有参考价值,需要的朋友可以了解下。
主要为大家详细介绍了C语言之复杂链表的复制,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的 深拷贝。 我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, ...
4:一般的处理新建一些节点,链表都能实现这个功能;但是为了节省空间复杂度,一般尽量利用单一变量在原链表上做出修改。除非有些情况无法处理,新建数组或者链表存储数据。 5:所以对于新建链表,一般仍然...
剑指 Offer 35. 复杂链表的复制图解 链表的深拷贝剑指 Offer 35. 复杂链表的复制(哈希表 / 拼接与拆分,清晰图解)看了dfs的题解,感觉df
复杂链表的复制.py 二叉搜索树与双向链表.py 序列化二叉树.py 字符串的排列.py 数组中出现次数超过一半的数字.py 最小的k个数.py 连续子数组的最大和.py n整数中1出现的次数.py 数字序列中的某一位数字.py 把数组拍...
链表的难点在于必须复制链表处理函数来处理不同的对象,即便逻辑是完全相同的。 基础 让我们从一个非常简单的例子开始,如下: int n; 这个应该被理解为“declare n as an int”(n是一个int型的变量)...