网站价格套餐,品牌建设计划,保健品网站可以做网站,如何查公司注册信息及法人面试题26#xff1a;复杂链表的复制 题目#xff1a;请实现函数ComplexListNodeClone#xff08;ComplexListNodepHead#xff09;#xff0c;复制一个复杂链表。在复杂链表中#xff0c;每个结点除了有一个m_pNext指针指向下一个结点外#xff0c;还有一个m_pSibling 指…面试题26复杂链表的复制 题目请实现函数ComplexListNodeCloneComplexListNodepHead复制一个复杂链表。在复杂链表中每个结点除了有一个m_pNext指针指向下一个结点外还有一个m_pSibling 指向链表中的任意结点或者NULL。结点的C定义如下
struct ComplexListNode
{int value;ComplexListNode * next;ComplexListNode * sibling;
};第一步:
代码如下:
void CloneNodes(ComplexListNode *pHead)
{ComplexListNode *pNode pHead;while (pNode ! nullptr){ComplexListNode *pCloned new ComplexListNode();pCloned-value pNode-value;pCloned-next pNode-next;pCloned-sibling nullptr;pNode-next pCloned;pNode pCloned-next;}
}第二步: 代码如下:
void ConnectSiblingNodes(ComplexListNode *pHead)
{ComplexListNode *pNode pHead;while (pNode ! nullptr){ComplexListNode *pCloned pNode-next;if (pNode-sibling ! nullptr){pCloned-sibling pNode-sibling-next;}pNode pCloned-next;}
}第三步: 代码如下:
ComplexListNode *ReconnectNodes(ComplexListNode *pHead)
{ComplexListNode *pNode pHead;ComplexListNode *pClonedHead nullptr;ComplexListNode *pClonedNode nullptr;if (pNode ! nullptr){pClonedHead pClonedNode pNode-next;pNode-next pClonedNode-next;pNode pNode-next;}while (pNode ! nullptr){pClonedNode-next pNode-next;pClonedNode pClonedNode-next;pNode-next pClonedNode-next;pNode pNode-next;}return pClonedHead;
}完整代码如下:
#include iostream
using namespace std;struct ComplexListNode
{int value;ComplexListNode * next;ComplexListNode * sibling;
};void CloneNodes(ComplexListNode *pHead)
{ComplexListNode *pNode pHead;while (pNode ! nullptr){ComplexListNode *pCloned new ComplexListNode();pCloned-value pNode-value;pCloned-next pNode-next;pCloned-sibling nullptr;pNode-next pCloned;pNode pCloned-next;}
}void ConnectSiblingNodes(ComplexListNode *pHead)
{ComplexListNode *pNode pHead;while (pNode ! nullptr){ComplexListNode *pCloned pNode-next;if (pNode-sibling ! nullptr){pCloned-sibling pNode-sibling-next;}pNode pCloned-next;}
}ComplexListNode *ReconnectNodes(ComplexListNode *pHead)
{ComplexListNode *pNode pHead;ComplexListNode *pClonedHead nullptr;ComplexListNode *pClonedNode nullptr;if (pNode ! nullptr){pClonedHead pClonedNode pNode-next;pNode-next pClonedNode-next;pNode pNode-next;}while (pNode ! nullptr){pClonedNode-next pNode-next;pClonedNode pClonedNode-next;pNode-next pClonedNode-next;pNode pNode-next;}return pClonedHead;
}ComplexListNode *Clone(ComplexListNode *pHead)
{CloneNodes(pHead);ConnectSiblingNodes(pHead);return ReconnectNodes(pHead);
}测试用例 ● 功能测试包括结点中的 m_pSibling 指向结点自身两个结点的m_pSibling形成环状结构链表中只有一个结点。 ● 特殊输入测试指向链表头结点的指针为NULL指针。 本题考点 ● 考查应聘者对复杂问题的思维能力。本题中的复杂链表是一种不太常见的数据结构而且复制这种链表的过程也较为复杂。我们把复杂链表的复制过程分解成三个步骤同时把每一个步骤都用图形化的方式表示出来这些方法都能帮助我们理清思路。写代码的时候我们为每一个步骤定义一个子函数最后在复制函数中先后调用者3个函数。有了这些清晰的思路之后再写代码就容易多了。 ● 考查应聘者分析时间效率和空间效率的能力。当应聘者提出第一种和第二种思路的时候面试官会提示此时在效率上还不是最优解。这个时候应聘者要能自己分析出这两种算法的时间复杂度和空间复杂度各是多少。
