面試題26：復(fù)雜鏈表的復(fù)制
題目：請實(shí)現(xiàn)函數(shù)ComplexListNodeClone（ComplexListNodepHead），復(fù)制一個(gè)復(fù)雜鏈表。在復(fù)雜鏈表中，每個(gè)結(jié)點(diǎn)除了有一個(gè)m_pNext指針指向下一個(gè)結(jié)點(diǎn)外，還有一個(gè)m_pSibling 指向鏈表中的任意結(jié)點(diǎn)或者NULL。結(jié)點(diǎn)的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); }

測試用例：
● 功能測試（包括結(jié)點(diǎn)中的 m_pSibling 指向結(jié)點(diǎn)自身，兩個(gè)結(jié)點(diǎn)的m_pSibling形成環(huán)狀結(jié)構(gòu)，鏈表中只有一個(gè)結(jié)點(diǎn)）。
● 特殊輸入測試（指向鏈表頭結(jié)點(diǎn)的指針為NULL指針）。
本題考點(diǎn)：
● 考查應(yīng)聘者對復(fù)雜問題的思維能力。本題中的復(fù)雜鏈表是一種不太常見的數(shù)據(jù)結(jié)構(gòu)，而且復(fù)制這種鏈表的過程也較為復(fù)雜。我們把復(fù)雜鏈表的復(fù)制過程分解成三個(gè)步驟，同時(shí)把每一個(gè)步驟都用圖形化的方式表示出來，這些方法都能幫助我們理清思路。寫代碼的時(shí)候，我們?yōu)槊恳粋€(gè)步驟定義一個(gè)子函數(shù)，最后在復(fù)制函數(shù)中先后調(diào)用者3個(gè)函數(shù)。有了這些清晰的思路之后再寫代碼，就容易多了。
● 考查應(yīng)聘者分析時(shí)間效率和空間效率的能力。當(dāng)應(yīng)聘者提出第一種和第二種思路的時(shí)候，面試官會(huì)提示此時(shí)在效率上還不是最優(yōu)解。這個(gè)時(shí)候應(yīng)聘者要能自己分析出這兩種算法的時(shí)間復(fù)雜度和空間復(fù)雜度各是多少。

總結(jié)

以上是生活随笔為你收集整理的[剑指offer]面试题26：复杂链表的复制的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。