题目:有一个复杂链表,其结点除了有一个m_pNext指针指向下一个结点外,还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下:
struct ComplexNode
{
int m_nValue;
ComplexNode* m_pNext;
ComplexNode* m_pSibling;
};
下图是一个含有5个结点的该类型复杂链表。图中实线箭头表示m_pNext指针,虚线箭头表示m_pSibling指针。为简单起见,指向NULL的指针没有画出。
首先在原链表的每个节点后都创建一个对应的节点,初始化的时候m_pSibling=NULL
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的值,A中新的节点1的m_pSibling 等于原节点中1的m_pSibling的m_pNext
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;
}
}
构造完新链表之后,提取链表
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;
}
分享到:
相关推荐
程序员面试题精选 100 题(01)-把二元查找树转变成排序的 双向链表 题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点, 只调整指针的指向。 程序员面试题精选 100 题...
由第三方作者花费大量时间收集并整理散落在茫茫网络中的面经,并从中精选出若干具有代表性的技术类的面试题展开讨论,希望能给读者带来一些启发 例如; 把二元查找树转变成排序的双向链表 设计包含min函数的栈 把...
前言随着高校的持续扩张,每年应届毕业生的数目都在不断增长,伴随而来的是应届毕业生的就业压力也越来越大。在这样的背景下,就业变成一个买方市场的趋势越来越明显。为了
面试题5:检测一个较大的单向链表是否带环 10.3 双向链表 面试题6:按要求构造一个双向链表 面试题7:编程实现双链表插入新结点 面试题8:编程实现双链表删除指定结点 10.4 栈和队列 面试题9:简述队列和栈的异同 ...
程序员面试 100题 前60题 里面的内容主要是 数据结构方面 : 数组 链表 二叉树
一个既长又复杂的进程可以考虑分为多个线程,成为几个独立或半独 立的运行部分,这样的程序会利于理解和修改。 其他情况都使用单线程。 11.Windows是内核级线程么。 答:见下一题 12.Linux有内核级线程么。 答:...
C++面试题 参考:http://blog.csdn.net/Ghost90/archive/2009/04/22/4099672.aspx 整理:松鼠 时间:2009-5-8 1、const 有什么用途?(请至少说明两种) 答: (1)可以定义 const 常量 (2)const可以修饰函数的...
通常性能上较ArrayList差,而LinkedList使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但是插入数据时只需要记录本项的前后项即可,所以插入速度较快。 8、EJB是基于哪些技术实现的?并说出Session...
道常见的程序员面试题,这些题目偏向中低难度,是入门上手不错的选择。另外这些题目基本上在各大 OJ 上也都有,可以非常方便地提交自己的实现进行练手。 如果刚开始练习算法题目,「剑指 Offer」是个不错的切入点。...
超级有影响力的Java面试题大全文档 1.抽象: 抽象就是忽略一个主题中与当前目标无关的那些方面,以便更充分地注意与当前目标有关的方面。抽象并不打算了解全部问题,而只是选择其中的一部分,暂时不用部分细节。...
1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char const*...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
不多说了 直接上目录: 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 ...84. C语言惠通面试题 428 85. C语言常用宏定义 450 有需要的朋友可以根据需求下载,内容为WORD格式的,绝对清晰
高级进阶c语言教程 目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
目录 1. C 语言中的指针和内存泄漏 5 2. C语言难点分析整理 10 3. C语言难点 18 4. C/C++实现冒泡排序算法 32 5. C++中指针和引用的区别 35 6. const char*, char ...84. C语言惠通面试题 428 85. C语言常用宏定义 450
实例032 递归算法的经典面试题 39 实例033 制作一个数字猜猜看小游戏 40 实例034 使用goto语句在数组中搜索指定图书 42 第3章 字符串处理技术 44 3.1 字符及字符串转换 45 实例035 将字母全部转换为大写或小写 45 ...