C語言複雜鏈表深度複製：O(1) 空間優雅解法

編輯：關於C語言

C語言複雜鏈表深度複製：O(1) 空間優雅解法

複雜鏈表（Complex List）每個節點除擁有 next 指標外，還額外擁有一個 random 指標，可指向鏈表中任意節點或 NULL。深度複製此類鏈表的挑戰在於：如何在不使用額外雜湊表（O(N) 空間）的情況下，正確重建 random 指向關係。本文介紹經典的「三步走」原地複製演算法，實現 O(N) 時間、O(1) 額外空間的完美複製。

節點結構定義

// ComplexList.h
#pragma once
typedef int DataType;

typedef struct ComplexNode {
    DataType _data;
    struct ComplexNode* _next;
    struct ComplexNode* _random;
} ComplexNode, *pComplexNode;

void BuyNode(pComplexNode& pNode, DataType x);
void PushBack(pComplexNode& pHead, DataType x);
void CopyComplexList(pComplexNode pHead, pComplexNode& NewpHead);
pComplexNode Find(pComplexNode pHead, DataType Data);
void PrintLinkList(pComplexNode pHead);

三步走複製演算法核心邏輯

// 複雜鏈表複製
void CopyComplexList(pComplexNode pHead, pComplexNode& NewpHead) {
    pComplexNode tmp = pHead;
    pComplexNode head = pHead;
    if (pHead == NULL) return;

    // 步驟 1：在每個原節點後插入其複製節點
    // 原: A->B->C  變: A->A'->B->B'->C->C'
    while (head != NULL) {
        tmp = head->_next;
        BuyNode(NewpHead, head->_data);  // 建立複製節點 NewpHead
        head->_next = NewpHead;          // 原節點 next 指向複製節點
        NewpHead->_next = tmp;           // 複製節點 next 指向原下一個節點
        head = tmp;                      // 移至下一個原節點
    }

    // 步驟 2：設定複製節點的 random 指標
    // 複製節點的 random = 原節點 random 的 next（即原 random 對應的複製節點）
    head = pHead;
    while (head != NULL) {
        tmp = head->_next;  // tmp 為複製節點
        if (head->_random == NULL) {
            tmp->_random = NULL;
        } else {
            tmp->_random = head->_random->_next;
        }
        head = head->_next->_next;  // 跳過複製節點，移至下一個原節點
    }

    // 步驟 3：拆分雙倍鏈表，還原原鏈表並提取複製鏈表
    head = pHead;
    NewpHead = head->_next;  // 複製鏈表頭節點
    while (head != NULL) {
        tmp = head->_next;           // tmp 為複製節點
        head->_next = tmp->_next;    // 還原原節點 next
        head = tmp->_next;           // 移至下一個原節點
        if (head == NULL) break;     // 原鏈表結束
        tmp->_next = head->_next;    // 設定複製節點 next 指向下一個複製節點
    }
}

輔助函數實作

// 建立節點
void BuyNode(pComplexNode& pNode, DataType x) {
    pNode = (pComplexNode)malloc(sizeof(ComplexNode));
    pNode->_data = x;
    pNode->_next = NULL;
    pNode->_random = NULL;
}

// 尾插建立鏈表
void PushBack(pComplexNode& pHead, DataType x) {
    pComplexNode tmp = pHead;
    if (pHead == NULL) {
        BuyNode(pHead, x);
        return;
    }
    while (tmp->_next != NULL) {
        tmp = tmp->_next;
    }
    BuyNode(tmp->_next, x);
}

// 查找節點
pComplexNode Find(pComplexNode pHead, DataType Data) {
    pComplexNode tmp = pHead;
    assert(pHead);
    while (tmp) {
        if (tmp->_data == Data) return tmp;
        tmp = tmp->_next;
    }
    return NULL;
}

// 列印鏈表
void PrintLinkList(pComplexNode pHead) {
    pComplexNode tmp = pHead;
    if (pHead == NULL) {
        printf("鏈表為空！\n");
    }
    while (tmp) {
        printf("%d ", tmp->_data);
        tmp = tmp->_next;
    }
    printf("\n");
}

測試驗證

// 主函數測試
#include <stdio.h>
#include "ComplexList.h"

void test1() {
    pComplexNode pHead = NULL, NewpHead = NULL;
    PushBack(pHead, 1);
    PushBack(pHead, 2);
    PushBack(pHead, 3);
    PushBack(pHead, 4);
    PrintLinkList(pHead);  // 1 2 3 4

    // 設定 random 指標
    Find(pHead, 1)->_random = Find(pHead, 3);
    Find(pHead, 2)->_random = Find(pHead, 4);
    Find(pHead, 3)->_random = Find(pHead, 2);
    Find(pHead, 4)->_random = Find(pHead, 1);

    CopyComplexList(pHead, NewpHead);
    PrintLinkList(NewpHead);  // 應輸出 1 2 3 4，且 random 關係完全一致
}

int main() {
    test1();
    return 0;
}