5.4.5展平链表.md

• 问题：

  • 给定一个链表的头节点，要求展平一个双向链表。这意味着将链表中的嵌套结构（比如 child 指针）转换为一个单一的链表。每个节点都是一个结构体，定义如下所示：

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

  • 例子：

    • 原输入：

    1 -> 2 -> 3
    |
    4 -> 5

    • 输出：

    1 -> 4 -> 5 -> 2 -> 3

  • 问题分析：

    1. 存在嵌套结构： 题目中的 child 指针，说明存在链表内部的嵌套结构；
    2. 整体与局部的关系： 嵌套的子链表结构与整体链表结构相似，可以将展平问题分解为先展平子链表，再将其连接到父链表的过程。
    3. 逐步简化问题： 在展平链表的问题中，可以通过逐一处理每个节点及其子链表来简化问题。
       1. 处理每一个节点：
          1. 情况一，为空，则终止
          2. 情况二，不为空，则将这个节点加入到结果列表里
             1. 检查节点是否有child，如果有，则继续检查子child
             2. 检查节点是否有next 节点，如果有，则继续检查next child
    4. 终止条件： 链表为空或没有子链表的节点。

  • 算法思想：递归+前序遍历

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

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

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

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

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

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

    Node* head = new Node{ nullptr, nullptr, nullptr, 1 };
    head->next = new Node{ nullptr, nullptr, nullptr, 2 };
    head->next->prev = head;
    head->next->next = new Node{ nullptr, nullptr, nullptr, 3 };
    head->next->next->prev = head->next;
    head->child = new Node{ nullptr, nullptr, nullptr, 4 };
    head->child->next = new Node{ 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
    }

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

    return 0;
}