One Problem ask by my Faculty! Can Anyone Help?

[Starshadow0707]

Flatten a Multilevel Doubly Linked List

Prob. Desc.

You are given a doubly linked list, where each node contains:

• An integer value val.
• A next pointer to the next node in the list.
• A prev pointer to the previous node in the list.
• A child pointer to another doubly linked list.

The child pointer may point to a separate doubly linked list, which may also contain one or more child pointers. This structure can be nested arbitrarily.

Write a function to flatten the list so that all nodes appear in a single-level doubly linked list. The flattened list should maintain the original order of nodes at each level.

Constraints

1. The number of nodes is in the range $([1, 10^3])$.
2. $( 0 \leq \text{Node.val} \leq 10^5 )$.
3. The list may contain multiple levels of nesting.
4. The child pointer may point to nullptr.

Example

Input:

1---2---3---4---5---6
        |
        7---8---9---10
            |
            11---12

Output:

1---2---3---7---8---11---12---9---10---4---5---6

Explanation:
The child list starting at node 3 is inserted between 3 and 4. Similarly, the child list of node 8 is inserted between 8 and 9.

[Hunterdii]

Approach 1: Iterative Depth-First Search (DFS)

Algorithm

1. Use a stack to store nodes that need to be processed later.
2. Traverse the list:
   • If a node has a child, push its next node (if exists) onto the stack.
   • Link the child list to the current node.
   • Clear the child pointer.
3. Continue processing nodes in the stack until it's empty.

Complexity

• Time Complexity: O(N), where (N) is the total number of nodes in the list (including child lists).
• Space Complexity: O(N), for the stack in the worst case.

Code Implementation (Python)

class Node:
    def __init__(self, val, prev=None, next=None, child=None):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child

def flatten(head):
    if not head:
        return None

    stack = []
    current = head

    while current:
        if current.child:
            # If there's a next node, push it to the stack
            if current.next:
                stack.append(current.next)
            # Link child list to the current node
            current.next = current.child
            current.child.prev = current
            current.child = None

        if not current.next and stack:
            # Pop the next node from the stack
            next_node = stack.pop()
            current.next = next_node
            next_node.prev = current

        current = current.next

    return head

# Helper function to print
def print_list(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    print(result)

# Example usage
if __name__ == "__main__":
    head = Node(1)
    head.next = Node(2, head)
    head.next.next = Node(3, head.next)
    head.next.next.next = Node(4, head.next.next)
    head.next.next.child = Node(7)
    head.next.next.child.next = Node(8, head.next.next.child)
    head.next.next.child.next.child = Node(11)
    head.next.next.child.next.child.next = Node(12, head.next.next.child.next.child)

    flattened = flatten(head)
    print_list(flattened)

Approach 2: Recursive Depth-First Search (DFS)

Algorithm

1. Use recursion to flatten each node's child list.
2. When a node with a child is encountered:
   • Flatten the child list.
   • Insert the flattened child list between the current node and its next node.
3. Return the tail node of the flattened list to maintain connections.

Complexity

• Time Complexity: O(N), where (N) is the total number of nodes.
• Space Complexity: O(D), where D is the maximum depth of the nested list (recursion stack).

Code Implementation (Python)

class Node:
    def __init__(self, val, prev=None, next=None, child=None):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child

def flatten_recursively(head):
    if not head:
        return None

    def dfs(node):
        current = node
        last = node

        while current:
            next_node = current.next
            if current.child:
                # Flatten the child list
                child_head, child_tail = dfs(current.child)

                # Connect the current node to the child list
                current.next = child_head
                child_head.prev = current
                current.child = None

                # Connect the tail of the child list to the next node
                if next_node:
                    child_tail.next = next_node
                    next_node.prev = child_tail

                last = child_tail
            else:
                last = current

            current = next_node

        return node, last

    dfs(head)
    return head

# Helper function to print
def print_list(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    print(result)

# Example usage
if __name__ == "__main__":
    head = Node(1)
    head.next = Node(2, head)
    head.next.next = Node(3, head.next)
    head.next.next.next = Node(4, head.next.next)
    head.next.next.child = Node(7)
    head.next.next.child.next = Node(8, head.next.next.child)
    head.next.next.child.next.child = Node(11)
    head.next.next.child.next.child.next = Node(12, head.next.next.child.next.child)

    flattened = flatten_recursively(head)
    print_list(flattened)

✨ Solved Questions in CPP with Same Approach

(Click to expand)

Approach 1: Iterative Depth-First Search (DFS)

Code Implementation (C++)

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node* prev;
    Node* child;
    Node(int _val) : val(_val), next(nullptr), prev(nullptr), child(nullptr) {}
};

Node* flatten(Node* head) {
    if (!head) return nullptr;

    Node* dummy = new Node(0);
    Node* prev = dummy;
    Node* curr = head;

    // To keep track of nodes to visit
    stack<Node*> stk;
    stk.push(curr);

    while (!stk.empty()) {
        curr = stk.top();
        stk.pop();

        // Connect current node to previous node
        prev->next = curr;
        curr->prev = prev;

        // If next exists, push it onto the stack
        if (curr->next) stk.push(curr->next);

        // If child exists, push it onto the stack
        if (curr->child) {
            stk.push(curr->child);
            curr->child = nullptr; // Clear the child pointer
        }

        prev = curr;
    }

    // Remove dummy node
    dummy->next->prev = nullptr;
    return dummy->next;
}

// Helper function to print the doubly linked list
void printList(Node* head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // Create nodes
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->prev = head;
    head->next->next = new Node(3);
    head->next->next->prev = head->next;
    head->next->next->child = new Node(7);
    head->next->next->child->next = new Node(8);
    head->next->next->child->next->prev = head->next->next->child;
    head->next->next->child->next->child = new Node(11);
    head->next->next->child->next->child->next = new Node(12);

    Node* flattened = flatten(head);
    printList(flattened);

    return 0;
}

Approach 2: Recursive Depth-First Search (DFS)

Code Implementation (C++)

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node* prev;
    Node* child;
    Node(int _val) : val(_val), next(nullptr), prev(nullptr), child(nullptr) {}
};

Node* flattenDFS(Node* head) {
    if (!head) return nullptr;

    Node* curr = head;
    Node* tail = nullptr;

    while (curr) {
        Node* next = curr->next;

        if (curr->child) {
            Node* childHead = flattenDFS(curr->child);

            // Connect current node to the child list
            curr->next = childHead;
            childHead->prev = curr;
            curr->child = nullptr;

            // Find the tail of the child list
            Node* childTail = childHead;
            while (childTail->next) {
                childTail = childTail->next;
            }

            // Connect the tail of the child list to the next node
            if (next) {
                childTail->next = next;
                next->prev = childTail;
            }

            tail = childTail;
        } else {
            tail = curr;
        }

        curr = next;
    }

    return head;
}

// Helper function to print the doubly linked list
void printList(Node* head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // Create nodes
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->prev = head;
    head->next->next = new Node(3);
    head->next->next->prev = head->next;
    head->next->next->child = new Node(7);
    head->next->next->child->next = new Node(8);
    head->next->next->child->next->prev = head->next->next->child;
    head->next->next->child->next->child = new Node(11);
    head->next->next->child->next->child->next = new Node(12);

    Node* flattened = flattenDFS(head);
    printList(flattened);

    return 0;
}

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Iterative DFS	O(N)	O(N)	Uses a stack for tracking. Preferred for simplicity.
Recursive DFS	O(N)	O(D)	Cleaner but may lead to stack overflow for deep nesting.

Above Both the approaches are efficient and provide correct results. The iterative method is often preferred for practical use as it avoids potential recursion limits.