前言：
適逢妹紙在復習，順便見我也在學習，便問了這樣一個問題【她是怎麼想到這個的】。
有一個很多層的鏈表，嗯，雙向的吧，然後每個節點還有個指針指向了它的子鏈表，單獨的，如果有的話；同一層的子鏈表，嗯，也是雙向鏈接的吧；然後怎麼將它們比較快的變成只有一條主鏈表呢？關系還是保持不變的哦。對了，可以展開的話，順便也還原回去吧。。。
為了不在妹紙面前慫，毅然決然拿起紙幣就左圖右畫了起來，經過快二十分鐘的左移右移，加上點必要代碼，算是給妹紙解釋好了，差點就跪了。
過程：
首先是雙向的，那就好辦多了，之前遇到的很多問題都是單向的，先畫個多層鏈表示意圖好了；問妹紙是不是這樣的，她說差不多。。。
然後想一下以什麼樣的順序存放吧，可以是父子父子這樣一直連下去的，也可以是橫著過去，一行一行的放的，感覺一層一層來改變的順序要少一點，那就那樣吧。
肯定是要從頭開始遍歷的，所以時間復雜度最少是O(n)；如果有子鏈表就把它追加到現有的尾指針那裡；那麼新的尾指針應該在哪裡呢？新加的那一個子節點？不，不是那個，因為我們要把整一層都放在一起，那樣的話，就要子鏈表的最後一個節點作為新的尾指針了，那樣一整塊就被追加過去了。
接著next下去繼續遍歷，同樣是有子鏈表就追加，原第一層的完了就從追加的節點繼續，然後一層一層就連起來了。
展開了，是時候考慮一下怎麼變回去了？！
逆向思維的話就是從尾部開始遍歷回去，反正是雙向的，但是從尾部開始的話，該怎麼判定這個節點是不是子節點呢？要確認的話估計只能從頭指針開始遍歷匹配是誰的子節點了，那樣務必要遍歷多次，不太科學；
也可以是用東西把所有的子節點都存起來，那樣從尾部遍歷就不用每次都遍歷了，但是又要多用東西耶，可能還有更好的方法；
要不還是從頭開始！
遍歷鏈表，如果有子鏈表就將它從主鏈表那裡切斷開來，但是又不能就這樣返回了，不然到了原來第一層那裡就沒後續節點了，那就只能分離第一層的子鏈表了；對了，那就遞歸，從子鏈表那繼續切斷，如果有它也有子鏈表的話。
那麼尾指針怎麼安放好呢？想想因為它會不斷從後面分離，不影響前面的，那就直接將遍歷到的最後一個作為尾指針好了，到時候就是到原第一層的末尾了。
既然想好了，那就試試實現吧。
代碼：
/*********************
Author:AnnsShadow
Time = 2015-12-03
*********************/
#include <stdio.h>
#include <stdlib.h>
//每個節點的定義
typedef struct chainNode
{
struct chainNode *next;
struct chainNode *previous;
struct chainNode *child;
int value;
} chainNode;
/**
為什麼tail要用指向指針的指針，因為要修改它啊！
不然在函數裡面改了影響不了原來的哦！
**/
//在鏈表末尾追加鏈接
void appendChain(chainNode *child, chainNode **tail);
//展開多層鏈表，使之成為一層
void expandChain(chainNode *head, chainNode **tail);
//將子鏈表從一層鏈表中分離
void seperateChild(chainNode *childHead);
//將一層鏈表還原成多層鏈表
void unexpandChain(chainNode *head, chainNode **tail);
int main()
{
chainNode *head, *tail;
//構造對應的測試多層鏈表
/**
Some codes;
**/
expandChain(head, &tail);
unexpandChain(head, &tail);
return 0;
}
void appendChain(chainNode *child, chainNode **tail)
{
//將當前指針賦值為傳入的子鏈表
chainNode *currentNode = child;
//原尾指針的下一個賦值為傳入的子鏈表
(*tail)->next = child;
//子鏈表的上一個賦值為原尾指針
child->previous = *tail;
//遍歷當前子鏈表直到最後
for(; currentNode->child; currentNode = currentNode->next);
//賦值產生新的尾指針
*tail = currentNode;
}
void expandChain(chainNode *head, chainNode **tail)
{
//將當前指針指向鏈表頭指針
chainNode *currentNode = head;
//當前指針不為NULL
while(currentNode)
{
//如果當前指針有子鏈表
if(currentNode->child)
{
//將其追加到鏈表的尾部
appendChain(currentNode->child, tail);
}
//指向下一個指針
currentNode = currentNode->next;
}
}
void seperateChild(chainNode *childHead)
{
//將當前指針賦值為子鏈表的頭指針
chainNode *currentNode = childHead;
//當前指針不為空
while(currentNode)
{
//如果當前指針有子鏈表
if(currentNode->child)
{
//將之前追加到指針‘下一個’的值取消
//也就是切斷鏈表
currentNode->child->previous->next = NULL;
//子鏈表從主鏈表分離
currentNode->child->previous = NULL;
//如果當前指針有子鏈表則繼續分離
seperateChild(currentNode->child);
}
//指向下一個指針
currentNode = currentNode->next;
}
}
void unexpandChain(chainNode *head, chainNode **tail)
{
//將當前指針賦值為主鏈表頭指針
chainNode *currentNode = head;
//開始分離
seperateChild(head);
//遍歷主鏈表到末尾
for(; currentNode->next; currentNode = currentNode->next);
//重新賦值尾指針
*tail = currentNode;
}
後記：
妹紙覺得答案挺滿意的，然後就問，要是是單向呢？
我就答，那就記住每次遍歷到哪裡好了；
再問，要是多層的結構是這樣的呢？
我再答：那樣連起來啊，也是有子鏈表就追加，而且可以一次追加整一層，不過要記住其中的有子鏈表的位置，那樣好像又有開銷了，诶，記住第一個就行了，反正一層都連起來了。
妹紙會心一笑。
