_430. Flatten a Multilevel Doubly Linked List.md

430. Flatten a Multilevel Doubly Linked List

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 27, 2024

Last updated : June 27, 2024

---

Related Topics : Linked List, Depth-First Search, Doubly-Linked List

Acceptance Rate : 60.54 %

---

Solutions

• m430.cpp
• m430.java

C++

m430.cpp

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

class Solution {
public:
    Node* flatten(Node* head) {
        if (!head) {
            return NULL;
        }

        if (!head->child) {
            head->next = flatten(head->next);
            return head;
        }

        if (!head->next) {
            head->next = flatten(head->child);
            head->child = NULL;
            head->next->prev = head;
            return head;
        }

        Node* holder = head->next;
        head->next = flatten(head->child);
        head->next->prev = head;
        head->child = NULL;

        Node* output = head;

        while (head->next) {
            head = head->next;
        }

        head->next = flatten(holder);
        head->next->prev = head;

        return output;
    }
};

Java

m430.java

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

class Solution {
    public Node flatten(Node head) {
        if (head == null) {
            return null;
        }

        if (head.child == null) {
            head.next = flatten(head.next);
            return head;
        }

        if (head.next == null) {
            head.next = flatten(head.child);
            head.child = null;
            head.next.prev = head;
            
            return head;
        }

        Node holder = head.next;
        head.next = flatten(head.child);
        head.next.prev = head;
        head.child = null;

        Node output = head;
        while (head.next != null) {
            head = head.next;
        } 
        head.next = flatten(holder);
        head.next.prev = head;

        return output;
    }
}