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

题目：

题解：

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

#define INIT_CAPACITY 4

class 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;
    }

    //Pop
    Node* 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;
    }

    //Push
    void 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;    
    }
};

原文地址：https://blog.csdn.net/m0_59237910/article/details/142447770

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！