題目

　　請實現函數 ComplexListNode clone(ComplexListNode head)，復制一個復雜鏈表。在復雜鏈表中，每個結點除了有一個 next 域指向下一個結點外，還有一個 sibling 指向鏈表中的任意結點或者 null。

分析

　　解題參見http://wiki.jikexueyuan.com/project/for-offer/question-twenty-six.html

　　引用

　　

　　圖 4.8 是一個含有 5 個結點的復雜鏈表。圖中實線箭頭表示 next 指針，虛線箭頭表示 sibling 指針。為簡單起見，指向 null 的指針沒有畫出。

　　

　　在不用輔助空間的情況下實現 O(n)的時間效率。

　　第一步：仍然是根據原始鏈表的每個結點N 創建對應的 N’。把 N’鏈接在N的后面。圖 4.8 的鏈表經過這一步之后的結構，如圖 4.9 所示。

　　　　

　　第二步：設置復制出來的結點的 sibling。假設原始鏈表上的 N 的 sibling 指向結點 S，那么其對應復制出來的 N’是 N的 pext 指向的結點，同樣 S’也是 S 的 next 指向的結點。設置 sibling 之后的鏈表如圖 4.10 所示。

　　

　　第三步：把這個長鏈表拆分成兩個鏈表。把奇數位置的結點用 next 鏈接起來就是原始鏈表，把偶數位置的結點用 next 鏈接起來就是復制 出來的鏈表。圖 4.10 中的鏈表拆分之后的兩個鏈表如圖 4.11 所示。

　　

代碼

1 struct CListNode 2 { 3 char value; 4 CListNode* pNext; 5 CListNode* pSibLing; 6 }; 7 8 CListNode* CopyComplexList(CListNode* head) 9 { 10 if (!head) 11 { 12 throw std::exception("Invalid Input."); 13 } 14 15 CListNode* node=head; 16 while(node!=NULL) 17 { 18 CListNode* cnode=new CListNode(); 19 cnode->value=node->value; 20 cnode->pNext=node->pNext; 21 node->pNext=cnode; 22 node=cnode->pNext; 23 } 24 25 node=head; 26 CListNode* cnode; 27 while (node!=NULL) 28 { 29 cnode=node->pNext; 30 31 if (node->pSibLing) 32 { 33 cnode->pSibLing=node->pSibLing->pNext; 34 }else 35 { 36 cnode->pSibLing=NULL; 37 } 38 39 node=cnode->pNext; 40 } 41 42 //split the list 43 node=head; 44 CListNode* chead=head->pNext; 45 while (node!=NULL) 46 { 47 cnode=node->pNext; 48 49 node->pNext=cnode->pNext; 50 if (node->pNext) 51 { 52 cnode->pNext=node->pNext->pNext; 53 }else 54 { 55 cnode->pNext=NULL; 56 } 57 58 node=node->pNext; 59 } 60 61 return chead; 62 }

?

轉載于:https://www.cnblogs.com/wangzaizhen/p/5272615.html

總結

以上是生活随笔為你收集整理的算法题26 复杂链表的复制的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。