C语言 | Leetcode C语言题解之第430题扁平化多级双向链表

题目：

题解：

/*
// Definition for a Node.
class Node {
public:int val;Node* prev;Node* next;Node* child;
};
*/#define INIT_CAPACITY 4class Solution {
public:struct c_stack{Node** array;int top;int capacity;};//创建栈struct c_stack* StackCreate(){struct c_stack* obj = (struct c_stack*)malloc(sizeof(struct c_stack));obj->array = (Node**)malloc(sizeof(Node*) * INIT_CAPACITY);obj->top = 0;obj->capacity = INIT_CAPACITY;return obj;}//PopNode* StackPop(struct c_stack* obj){if (obj->top == 0)return NULL;return obj->array[--obj->top];}//给栈扩容void ExetendCapacity(struct c_stack* node){Node** temp = (Node**)realloc(node->array, sizeof(Node*) * (node->capacity + 4));if (NULL == temp){perror("realloc fail");return;}node->array = temp;node->capacity += 4;}//Pushvoid StackPush(struct c_stack* node, Node* x){if (node->top == node->capacity)ExetendCapacity(node);node->array[node->top++] = x;}Node* flatten(Node* head) {//这个栈用来储存child不为nullptr的节点的next, 即如果cur->child != NULL, 那就把cur->next入栈struct c_stack* nextNodeStack = StackCreate();//哨兵位的头节点Node* prevHead = (Node*)malloc(sizeof(Node));prevHead->next = head;Node* cur = head;Node* prevNode = prevHead;//只要cur不为NULL, 或者栈不为空, 就执行以下代码块while (cur || nextNodeStack->top){prevNode->next = cur;//即如果cur->child != NULL, 那就把cur->next入栈, 并将cur的child置为NULL, 并将cur与其原来的child建立双向关系if (cur->child != NULL){StackPush(nextNodeStack, cur->next);Node* child = cur->child;cur->child = NULL;cur = child;cur->prev = prevNode->next;}//否则, 如果cur->next为NULL, 则说明cur走到尽头了, 此时如果栈为空, 说明要把此时的cur与栈顶的节点建立双向关系, 但是如果栈顶的节点为NULL, 那就要一直把栈顶元素移除, 直到栈顶元素不为NULL, 或者栈为空else if (cur->next == NULL){// 如果栈为空, 说明所有元素都遍历完了, 就已经可以返回了if (nextNodeStack->top == 0){cur->prev = prevNode;cur = cur->next;}else{   cur = StackPop(nextNodeStack);//如果cur为NULL, 就一直移除栈顶元素, 并将其赋值给cur, 直到cur不为NULL, 或者栈为空while (NULL == cur && nextNodeStack->top){cur = StackPop(nextNodeStack);}// 如果是栈为空了, 并且cur仍然为NULL, 说明此前栈内元素全为NULL, 此时只需处理一下尾节点的next就可以返回了if (cur == NULL){prevNode->next->next = NULL;break;}cur->prev = prevNode->next;}}// 如果上述两个条件均不满足, 即cur是正常的节点, 直接赋值下一个, 然后继续循环else{cur = cur->next;}prevNode = prevNode->next;}//防止内存泄漏Node* ret = prevHead->next;free(prevHead);free(nextNodeStack->array);free(nextNodeStack);return ret;    }
};