algoadvance

Leetcode 430. Flatten a Multilevel Doubly Linked List

Problem Statement

You are given a doubly linked list, which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the below example.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]

Clarifying Questions

  1. What should be done with the child pointers after flattening?
    • After flattening, the child pointers should be set to nullptr since we are converting the structure to a single-level doubly linked list.
  2. What is the structure of the nodes in the list?
    • Each node has the following properties:
      • int val: the value of the node.
      • Node* prev: the previous node in the doubly linked list.
      • Node* next: the next node in the doubly linked list.
      • Node* child: the child node in the multilevel list.
  3. What should be returned?
    • The function should return the head of the flattened doubly linked list.

Strategy

  1. Iterate through each node in the list.
  2. Whenever a node with a child pointer is encountered:
    • Recursively flatten the child list.
    • Insert the flattened child list between the current node and the next node.
    • Adjust the prev and next pointers accordingly.
    • Set the child pointer to nullptr.
  3. Continue the process until the entire list is flattened.

Code

#include <iostream>

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

    Node() : val(0), prev(nullptr), next(nullptr), child(nullptr) {}
    Node(int _val) : val(_val), prev(nullptr), next(nullptr), child(nullptr) {}
    Node(int _val, Node* _prev, Node* _next, Node* _child) : val(_val), prev(_prev), next(_next), child(_child) {}
};

class Solution {
public:
    Node* flatten(Node* head) {
        if (!head) return nullptr;
        
        Node* curr = head;
        while (curr != nullptr) {
            // If the current node has a child, we need to flatten the child list
            if (curr->child) {
                // Keep track of the next node
                Node* next = curr->next;
                
                // Flatten the child list
                Node* childHead = flatten(curr->child);
                
                // Connect the current node to the head of the flattened child list
                curr->next = childHead;
                childHead->prev = curr;
                
                // Find the tail of the flattened child list
                Node* childTail = childHead;
                while (childTail->next != nullptr) {
                    childTail = childTail->next;
                }
                
                // Reconnect the tail of the flattened child list to the next node
                childTail->next = next;
                if (next != nullptr) {
                    next->prev = childTail;
                }
                
                // Set the child pointer to nullptr
                curr->child = nullptr;
                
                // Move the current pointer to the next node
                curr = next;
            } else {
                // Move to the next node if there is no child
                curr = curr->next;
            }
        }
        
        return head;
    }
};

Time Complexity

The time complexity of this solution is O(N), where N is the total number of nodes in the multilevel doubly linked list. This is because each node is visited exactly once during the flattening process.

The auxiliary space used by the recursive stack is dependent on the maximum depth of the multilevel structure, which in the worst case could be O(N). However, if the list is mostly flat, the auxiliary space will be much less.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI