多層鏈表展開與還原算法：雙向鏈表子鏈表扁平化完整實現

編輯：關於C語言

算法挑戰：多層雙向鏈表的無損扁平化與還原

面對「妹紙」提出的算法挑戰：將擁有子鏈表指針的多層雙向鏈表，就地轉換為單層主鏈表，並能完美還原。本文記錄從圖解推演到代碼實現的完整思維過程，包含 O(n) 時間複雜度的展開算法、遞歸分離還原算法，及單向鏈表變體討論。

數據結構定義

typedef struct ChainNode {
    struct ChainNode *next;      // 同層下一節點
    struct ChainNode *previous;  // 同層上一節點
    struct ChainNode *child;     // 子鏈表頭節點
    int value;                   // 數據域
} ChainNode;

結構特徵：

主鏈表橫向雙向鏈接
每個節點可通過 child 指向一個獨立的子鏈表（同樣雙向）
子鏈表節點亦可擁有自己的 child，形成多層樹狀結構

算法一：展開 — 層序追加尾部法

核心思想

維護一個 全局尾指針，始終指向當前扁平化鏈表的最後節點
從頭遍歷主鏈表，遇到 child 非空，將整個子鏈表**整體追加**到尾部
更新尾指針為該子鏈表的**最後一個節點**
繼續遍歷（包含新追加的節點），直到無子鏈表

關鍵圖解

多層鏈表結構示意

展開後扁平化結構

核心代碼

// 追加子鏈表到尾部，更新尾指針
void appendChain(ChainNode *child, ChainNode **tail) {
    ChainNode *curr = child;
    (*tail)->next = child;      // 原尾連接子鏈表頭
    child->previous = *tail;    // 子鏈表頭回指原尾
    
    // 遍歷到子鏈表末尾
    while (curr->next) curr = curr->next;
    *tail = curr;               // 更新全局尾指針
}

// 主展開函數
void expandChain(ChainNode *head, ChainNode **tail) {
    ChainNode *curr = head;
    while (curr) {
        if (curr->child) {
            appendChain(curr->child, tail);
        }
        curr = curr->next;      // 繼續遍歷（含新追加部分）
    }
}

算法二：還原 — 遞歸分離法

逆向思維失敗嘗試

從尾部回溯：難以判斷節點是否為子鏈表頭（需從頭遍歷匹配，O(n²)）
額外空間記錄子鏈表頭：違反「就地」要求，增加空間複雜度

正向遞歸分離（最終方案）

從頭遍歷，發現 child 非空
切斷連接：將子鏈表從主鏈表分離（修正 previous/next 指針）
遞歸處理：對分離出的子鏈表調用同樣的分離函數
最終重新計算尾指針（遍歷到主鏈表末尾）

核心代碼

// 遞歸分離子鏈表
void separateChild(ChainNode *childHead) {
    ChainNode *curr = childHead;
    while (curr) {
        if (curr->child) {
            // 切斷：子鏈表頭的 previous 指向的節點 next 置 NULL
            curr->child->previous->next = NULL;
            // 子鏈表頭 previous 置 NULL
            curr->child->previous = NULL;
            // 遞歸處理子鏈表
            separateChild(curr->child);
        }
        curr = curr->next;
    }
}

// 還原主入口
void unexpandChain(ChainNode *head, ChainNode **tail) {
    separateChild(head);  // 從主鏈表頭開始遞歸分離
    // 重新尋找尾指針
    ChainNode *curr = head;
    while (curr->next) curr = curr->next;
    *tail = curr;
}

完整可編譯測試代碼

/********************* Author: AnnsShadow  Time: 2015-12-03 *********************/
#include 
#include 

typedef struct ChainNode {
    struct ChainNode *next;
    struct ChainNode *previous;
    struct ChainNode *child;
    int value;
} ChainNode;

void appendChain(ChainNode *child, ChainNode **tail);
void expandChain(ChainNode *head, ChainNode **tail);
void separateChild(ChainNode *childHead);
void unexpandChain(ChainNode *head, ChainNode **tail);

// 輔助：打印鏈表
void printChain(ChainNode *head, const char *tag) {
    printf("%s: ", tag);
    for (ChainNode *p = head; p; p = p->next) {
        printf("%d ", p->value);
    }
    printf("\n");
}

int main() {
    // 構建測試用多層鏈表
    ChainNode nodes[10];
    for (int i = 0; i < 10; ++i) {
        nodes[i].value = i+1;
        nodes[i].next = nodes[i].previous = nodes[i].child = NULL;
    }
    // 主鏈: 1-2-3-4
    for (int i = 0; i < 3; ++i) {
        nodes[i].next = &nodes[i+1];
        nodes[i+1].previous = &nodes[i];
    }
    // 節點2有子鏈: 5-6
    nodes[1].child = &nodes[4];
    nodes[4].next = &nodes[5];
    nodes[5].previous = &nodes[4];
    // 節點5有子鏈: 7
    nodes[4].child = &nodes[6];
    // 節點3有子鏈: 8-9-10
    nodes[2].child = &nodes[7];
    nodes[7].next = &nodes[8];
    nodes[8].previous = &nodes[7];
    nodes[8].next = &nodes[9];
    nodes[9].previous = &nodes[8];

    ChainNode *head = &nodes[0], *tail = &nodes[3];
    
    printChain(head, "原始主鏈(僅主層)");
    expandChain(head, &tail);
    printChain(head, "展開後扁平鏈表");
    unexpandChain(head, &tail);
    printChain(head, "還原後主鏈(僅主層)");
    
    return 0;
}

// ... 此處粘貼上述 appendChain, expandChain, separateChild, unexpandChain 實現 ...