5.4.6还原展平的链表.md

• 问题：还原5.4.5节被展平后的链表，输出第一层的所有结点。
  • 思路：
    1. 在展平链表之前，为每个节点添加一个额外的指针，例如 originalChild，用于存储节点原始的 child 指针。
    2. 在展平链表的过程中，将节点的 child 指针复制到相应的 originalChild 指针。
    3. 在展平链表之后，即展平链表已经完成，通过遍历每个节点，将 originalChild 指针用于还原原始的嵌套结构。

#include <iostream>
#include <list>
using namespace std;

struct Node{
    Node* next;
    Node* prev;
    Node* child;
    Node* originChild;
    int value;
};

void FlattenList(Node* node, std::list<Node>& res){
    if(node == nullptr){
        return;
    }

    res.push_back(*node);
    node->originChild = node->child;
    FlattenList(node->child, res);
    FlattenList(node->next, res);
}

std::list<Node> FlattenListHelper(Node* head){
    std::list<Node> res;
    FlattenList(head, res);
    return res;
}

void RestoreList(Node* head){
    Node* cur = head;
    while(cur != nullptr){
        cur->child = cur->originChild;
        cur = cur->next;
    }
}

int main() {
    // origin list:
    // 1 -> 2 -> 3
    // |
    // 4 -> 5

    Node* head = new Node{ nullptr, nullptr, nullptr, nullptr, 1 };
    head->next = new Node{ nullptr, nullptr, nullptr, nullptr, 2 };
    head->next->prev = head;
    head->next->next = new Node{ nullptr, nullptr, nullptr, nullptr, 3 };
    head->next->next->prev = head->next;
    head->child = new Node{ nullptr, nullptr, nullptr, nullptr, 4 };
    head->child->next = new Node{ nullptr, nullptr, nullptr, nullptr, 5 };
    head->child->next->prev = head->child;

    std::list<Node> flattenedList = FlattenListHelper(head);

    for (const Node& node : flattenedList) {
        cout << node.value << " ";// 1 -> 4 -> 5 -> 2 -> 3
    }
    cout << endl;

    RestoreList(head);
    
    auto it = head;
    while(it != nullptr){
        cout << it->value << " ";
        it = it->next;
    }
    cout << endl;

    // Clean up memory
    Node* current = head;
    while (current != nullptr) {
        Node* temp = current;
        current = current->next;
        delete temp;
    }

    return 0;
}