C++程序将多级链表展开

在日常的开发工作中，我们经常需要处理多级链表的数据结构。而多级链表在某些场合下可能需要展开为一维的单链表。比如，在一些题目中，假设输入的是多级链表，输出的内容则是展开后的一维链表。

那么，如何在C++中自动将多级链表展开为一维链表呢？

本文将针对此主题进行讲解，并提供示例代码，让读者更好地理解和掌握此技能。

多级链表的结构体定义

我们先定义一个多级链表的结构体，以便后续操作。结构体中包含了每个节点的val值、指向下一个节点的指针（next）以及指向下一级的指针（child）。

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     Node* next;
 *     Node* child;
 *     Node(int _val) {
 *         val = _val;
 *         next = NULL;
 *         child = NULL;
 *     }
 * };
 */

展开多级链表的实现

展开多级链表的实现原理是递归。对于每个节点，我们先判断它是否有child指针，如果有，则将它的child指针作为根节点继续递归展开，然后将返回的一维链表接到它的next指针上。最后，返回完整的一维链表。

class Solution {
public:
    Node* flatten(Node* head) {
        if(head == NULL) return head;
        Node* res = new Node(0);
        Node* cur = res;
        stack<Node*> st;
        st.push(head);
        while(!st.empty()){
            auto node = st.top(); st.pop();
            cur = cur->next = node;
            if(node->next != NULL)st.push(node->next);
            if(node->child != NULL)st.push(node->child), node->child = NULL;
        }
        res->next->prev = NULL;
        return res->next;
    }
};

代码中，我们使用了栈来完成递归的过程。具体来说，我们先将根节点入栈，然后在循环中不断从栈中取出节点进行判断和处理。

如果当前节点有child指针，则将child指针入栈，否则，如果当前节点有next指针，则将next指针入栈。同时将当前节点接到cur节点上。

最后，要记得将完整的一维链表的头结点的prev指针设置为NULL，以保证链表的正确性。返回res头结点的下一个节点即可。

示例代码

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

/**
 * Definition for a Node.
 **/
class Node {
public:
    int val;
    Node* next;
    Node* child;

    Node(int _val) {
        val = _val;
        next = NULL;
        child = NULL;
    }
};

class Solution {
public:
    Node* flatten(Node* head) {
        if(head == NULL) return head;
        Node* res = new Node(0);
        Node* cur = res;
        stack<Node*> st;
        st.push(head);
        while(!st.empty()){
            auto node = st.top(); st.pop();
            cur = cur->next = node;
            if(node->next != NULL)st.push(node->next);
            if(node->child != NULL)st.push(node->child), node->child = NULL;
        }
        res->next->prev = NULL;
        return res->next;
    }
};

int main()
{
    vector<int> data1{1,2,3,4,5,6}, data2{7,8,9,10}, data3{11,12};
    Node *head = new Node(0), *cur = head;
    for(auto it : data1) cur = cur->next = new Node(it);
    cur->next = new Node(0); cur = cur->next;
    cur->child= new Node(0);
    for(auto it : data2) cur = cur->next = new Node(it);
    cur = head->next;
    cur = cur->next->next->child = new Node(0);
    for(auto it : data3) cur = cur->next = new Node(it);
    Solution solution;
    Node *res = solution.flatten(head->next);
    while(res != NULL){
        cout << res->val << " ";
        res = res->next;
    }
    return 0;
}

代码中，我们先定义了一些数据，然后根据数据构建了一个多级链表。最后将这个链表的根节点输入展开函数Solution::flatten()，并输出展开后的一维链表的所有元素。

由于C++工程中的文件可能比较多，我们将整个代码放到了一个cpp文件中。在实际开发中，建议使用好的文件管理技巧，让代码的组织结构更加清晰合理。