複雜鏈表的複製

02-26

複雜鏈表的複製

在複雜鏈表中，每個節點除了有一個pnext指針指向下一個節點，還有一個psibling節點指向任意節點或者NULL。

思路：

1. 原始鏈表的每個節點創建對應的節點，新建的節點放在原始節點的後面。

2. 設置新建鏈表的psibling指針。

3. 把長鏈表拆成兩個鏈表。

參考代碼：

root@gt:/home/git/Code# ./a.out 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 root@gt:/home/git/Code# cat copy.cpp #include <iostream>using namespace std;struct CListNode{ int value; CListNode* pnext; CListNode* psibling;};void CloneNodes(CListNode* phead){ CListNode* pnode = phead; while(pnode) { CListNode* pclone = new CListNode(); pclone->value = pnode->value; pclone->pnext = pnode->pnext; pclone->psibling = NULL; pnode->pnext = pclone; pnode = pclone->pnext; }}void ConnectSiblingNodes(CListNode* phead){ CListNode* pnode = phead; while(pnode) { CListNode* pclone = pnode->pnext; if(pnode->psibling) { pclone->psibling = pnode->psibling->pnext; } pnode = pclone->pnext; }}CListNode* ReconnectNodes(CListNode* phead){ CListNode* pnode = phead; CListNode* pchead = NULL; CListNode* pclone = NULL; if(pnode) { pchead = pclone = pnode->pnext; pnode->pnext = pclone->pnext; pnode = pnode->pnext; } while(pnode) { pclone->pnext = pnode->pnext; pclone = pclone->pnext; pnode->pnext = pclone->pnext; pnode = pnode->pnext; } return pchead;}CListNode* CListCopy(CListNode* phead){ CloneNodes(phead); ConnectSiblingNodes(phead); return ReconnectNodes(phead);}int main(){ CListNode* phead = NULL; for(int i = 0;i < 10;i++) { CListNode* pnode = new CListNode(); pnode->value = i; pnode->psibling = NULL; pnode->pnext = phead; phead = pnode; } CListNode* pnode = phead; for(int i = 0;i < 9;i++) { pnode->pnext->psibling = pnode; pnode = pnode->pnext; } CListNode* pchead = CListCopy(phead); pnode = pchead; while(pnode) { cout << pnode->value << " "; pnode = pnode->pnext; } cout << endl; pnode = pchead->pnext; for(int i = 0;i < 9;i++) { cout << pnode->psibling->value << " "; pnode = pnode->pnext; } cout << endl; return 0;}