[다시예정] Flatten a Multilevel Doubly Linked List

Flatten a Multilevel Doubly Linked List

내가 푼 것

못품

문제점

• 문제를 잘못 이해했다.
• 재귀 못한다.
• dfs 제대로 구현을 못한다.
• prev 값을 넣어줘야하는 것을 몰랐다.(문제이해잘못에 포함)

베스트

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

class Solution {
public:
    Node* flatten(Node* head) {
        Node* temp=head;
        stack<Node*> st;
        while (head!=NULL) {
            if (head->child!=NULL) {
                if(head->next != NULL)
                    st.push(head->next);
                head->next = head->child;
                head->next->prev = head;
                head->child = NULL;
            }
            if (head->next == NULL && !st.empty()) {
                head->next = st.top();
                st.pop();
                head->next->prev = head;
            }
            head = head->next;
        }
        return temp;
    }
};

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

class Solution {
public:
    Node* flatten(Node* head) {
        if(head==NULL) return NULL;
        Node* curr=head;
        while (curr!=NULL) {
            if (curr->child != NULL) {
                if(curr->next != NULL) {
                    Node* temp = curr->next;
                    curr->next = curr->child;
                    curr->child->prev = curr;
                    curr->child = NULL;
                    Node* chi = curr->next;
                    while(chi->next != NULL){
                        chi = chi->next;
                    }
                    chi->next = temp;
                    temp->prev = chi;
                }
                else {
                    curr->next = curr->child;
                    curr->child->prev = curr;
                    curr->child = NULL;
                    Node* chi = curr->next;
                    while(chi->next != NULL){
                        chi = chi->next;
                    }
                    chi->next = NULL;
                }
            }
            curr = curr->next;
        }
       return head; 
    }
};