题目:有一个复杂链表,其结点除了有一个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题—何海涛》是一份详实的IT面试准备资料,由何海涛整理发布,旨在帮助应届毕业生和求职者准备面向微软、谷歌等知名科技公司的面试。此资料不仅收录了精选的100道面试题目,还提供了详细的解题...
程序员面试题精选100题 本资源是程序员面试题精选100题,涵盖了算法、数据结构、操作系统、计算机网络、数据库等多个领域。今天,我们将深入分析其中的一道题目,即将二元查找树转换成排序的双向链表。 知识点一:...
对于程序员面试,理解并能熟练应用这类问题的解决方案,展示了解数据结构和算法的能力,是评估应聘者编程技能的重要标准。同时,能清晰解释和分析递归过程,也是考察逻辑思维和问题解决能力的关键。
在这部分文档中,我们可以看到涉及到的IT知识点主要包括了数据结构和算法的内容。具体来说,文档中详细讨论了一个在程序员面试中...在程序员面试中,这样的问题可以帮助面试官评估应聘者是否具备解决复杂问题的潜质。
【程序员面试题精选100题【数据结构 /算法】】是针对求职程序员精心挑选的一系列面试题目,涵盖了数据结构和算法两大核心领域。这些题目旨在帮助应聘者提高面试技巧,提升对技术的理解,以便在激烈的就业市场竞争中...
本文档概述了程序员面试题精选100题,涵盖了C++面试题和笔试题,其中有一道典型的题目是将二元查找树转换成排序的双向链表。 知识点一:二元查找树(Binary Search Tree) * 二元查找树是一种特殊的树数据结构,它...
本题要求将二叉查找树转化为一个排序的双向链表,这一转换不仅考验应聘者对二叉树特性的理解,同时也考察了其对链表操作的熟练程度。 #### 1.2 题目描述 题目要求输入一棵二叉查找树,并将其转换为一个排序的双向...
例如,本文提到的《程序员面试题精选100题》就旨在为即将进入职场的程序员提供一系列经典的技术面试题目,帮助他们系统地复习相关知识和技术要点,从而提升面试表现。 #### 4. 具体案例分析:将二叉查找树转化为...
在程序员的面试过程中,面试题往往涵盖了许多技术领域,包括数据结构、算法、操作系统、网络、数据库等。这里我们重点讨论的是如何将一个二元查找树(Binary Search Tree, BST)转换成一个排序的双向链表,这是一个...
【知识点详解】 1. **二元查找树(Binary Search ... 这类问题通常出现在程序员的面试中,因为它测试了对数据结构的理解、递归思维以及解决问题的能力。理解和掌握这个问题的解法对于提升编程技巧和面试表现至关重要。