Flatten A Multilevel Doubly Linked List

                                            
class Solution {
    public Node flatten(Node head) {
        if (head == null) {
            return null;
        }
        
        Node pseudoHead = new Node();
        pseudoHead.next = head;
        
        flattenDFS(pseudoHead, head);
        
        pseudoHead.next.prev = null;
        return pseudoHead.next;
    }
    
    private Node flattenDFS(Node prev, Node curr) {
        if (curr == null) {
            return prev;
        }
        
        curr.prev = prev;
        prev.next = curr;
        
        Node tempNext = curr.next;
        
        Node tail = flattenDFS(curr, curr.child);
        curr.child = null;
        
        return flattenDFS(tail, tempNext);
    }
}

                                            
# Definition for a Node.
class Node(object):
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child

class Solution(object):
    def flatten(self, head):
        if not head:
            return head
        
        pseudo_head = Node(0, None, head, None)
        self.flatten_dfs(pseudo_head, head)
        pseudo_head.next.prev = None
        return pseudo_head.next
    
    def flatten_dfs(self, prev, curr):
        if not curr:
            return prev
        
        curr.prev = prev
        prev.next = curr
        
        temp_next = curr.next
        tail = self.flatten_dfs(curr, curr.child)
        curr.child = None

        return self.flatten_dfs(tail, temp_next)

                                            
public class Solution {
    public Node Flatten(Node head) {
        if(head == null) return null;
        
        Node curr = head;
        while(curr != null) {
            if(curr.child != null) {
                Node next = curr.next;
                Node child = Flatten(curr.child);
                curr.child = null;
                
                curr.next = child;
                child.prev = curr;
                
                while(child.next != null) {
                    child = child.next;
                }
                
                child.next = next;
                if(next != null) {
                    next.prev = child;
                }
            }
            curr = curr.next;
        }
        
        return head;
    }
}

                                            
/**
 * // Definition for a Node.
 * function Node(val,prev,next,child) {
 *    this.val = val;
 *    this.prev = prev;
 *    this.next = next;
 *    this.child = child;
 * };
 *
 * @param {Node} head
 * @return {Node}
 */
var flatten = function(head) {
    if (!head) return head;
    
    let stack = [head];
    let prev = null;
    
    while (stack.length > 0) {
        let current = stack.pop();
        
        if (current.next) stack.push(current.next);
        if (current.child) {
            stack.push(current.child);
            current.next = current.child;
            current.child.prev = current;
            current.child = null;
        }
        
        if (prev) {
            prev.next = current;
            current.prev = prev;
        }
        
        prev = current;
    }
    
    while (head.prev) {
        head = head.prev;
    }
    
    return head;
};

                                            
/**
 * Definition for node.
 * class Node {
 *     val: number
 *     prev: Node | null
 *     next: Node | null
 *     child: Node | null
 *     constructor(val?: number, prev?: Node, next?: Node, child?: Node) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.prev = (prev === undefined ? null : prev)
 *         this.next = (next === undefined ? null : next)
 *         this.child = (child === undefined ? null : child)
 *     }
 * }
 */
function flatten(head: Node | null): Node | null {
    if (!head) return head;
    
    let current: Node | null = head;
    while (current) {
        if (current.child) {
            let next = current.next;
            current.next = flatten(current.child);
            current.next.prev = current;
            current.child = null;
            while (current.next) {
                current = current.next;
            }
            current.next = next;
            if (next) {
                next.prev = current;
            }
        }
        current = current.next;
    }
    
    return head;
}

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

class Solution {
    /**
     * @param Node $head
     * @return Node
     */
    function flatten($head) {
        $stack = [];
        $current = $head;
        while ($current !== null || !empty($stack)) {
            if ($current->child !== null) {
                if ($current->next !== null) {
                    array_push($stack, $current->next);
                }
                $current->next = $current->child;
                $current->child->prev = $current;
                $current->child = null;
            }
            if ($current->next === null && !empty($stack)) {
                $current->next = array_pop($stack);
                $current->next->prev = $current;
            }
            $current = $current->next;
        }
        return $head;
    }
}

                                            
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Prev *Node
 *     Next *Node
 *     Child *Node
 * }
 */

func flatten(root *Node) *Node {
    if root == nil {
        return root
    }

    pseudoHead := &Node{}
    prev := pseudoHead
    stack := []*Node{root}

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        prev.Next = node
        node.Prev = prev

        if node.Next != nil {
            stack = append(stack, node.Next)
        }
        if node.Child != nil {
            stack = append(stack, node.Child)
            node.Child = nil
        }

        prev = node
    }

    pseudoHead.Next.Prev = nil
    return pseudoHead.Next
}

                                            
# Definition for a Node.
# class Node
#     attr_accessor :val, :prev, :next, :child
#     def initialize(val=nil, prev=nil, next_=nil, child=nil)
#         @val = val
#         @prev = prev
#         @next = next_
#         @child = child
#     end
# end

def flatten(head)
    return head if head.nil?
    
    sentinel = Node.new
    curr, prev = head, sentinel
    
    stack = []
    
    while curr != nil || !stack.empty?
        if curr && curr.child
            if curr.next
                stack.push(curr.next)
            end
            curr.next = curr.child
            curr.next.prev = curr
            curr.child = nil
        end
        
        if curr.nil? && !stack.empty?
            curr = stack.pop
        end
        
        prev.next = curr
        curr.prev = prev
        prev = curr
        curr = curr.next
    end
    
    sentinel.next.prev = nil
    sentinel.next
end

                                            
/**
 * Definition for a Node.
 * class Node(var _value: Int) {
 *   var value: Int = _value
 *   var prev: Node = null
 *   var next: Node = null
 *   var child: Node = null
 */

object Solution {
  def flatten(head: Node): Node = {
    var current = head
    while (current != null) {
      if (current.child != null) {
        val next = current.next
        val child = flatten(current.child)
        current.next = child
        child.prev = current
        current.child = null
        var temp = child
        while (temp.next != null) {
          temp = temp.next
        }
        temp.next = next
        if (next != null) {
          next.prev = temp
        }
      }
      current = current.next
    }
    head
  }
}

To solve this coding challenge of flattening a multilevel doubly linked list, we need to account for the following key points:

Each node in the doubly linked list can have a child pointer that points to another doubly linked list.
The child list nodes should appear directly after the current node and before the next node in the same level.
The solution should return the head of the flattened list, with all child pointers set to null.
Nodes are organized such that each node in the child list is woven into the main list according to their position.

We'll employ a depth-first search (DFS) strategy to handle the flattening. The reason DFS is suitable here is because we need to explore each child list completely before moving to the next nodes at the higher level.

# Explanation

To achieve the goal of flattening the multilevel doubly linked list:

Initialization : Start with a pseudo head node to ease edge cases where the list might be empty.
DFS Traversal : Use a helper function for depth-first traversal and linking nodes. This ensures all nodes are connected in the required order.
Recursive Linking : Recursively link all nodes by handling each node's child list first and then proceeding to the next node.
Child Handling and Link Adjustment : Make sure to detach child pointers after linking so the output list doesn't contain any remaining child pointers.

Step-by-Step Explanation

Base Case Handling :

If the head node is null, simply return.

Pseudo Head Node :

Create a pseudo head node (
pseudo_head

) as a convenient starting reference.
Set this node’s next pointer to point to the actual head node.

Recursive Depth-First Search :

Define a recursive helper function (
flatten_dfs

) that takes two parameters: the previous node (
prev

) and the current node (
curr

).
Within this function, perform the following actions:

Link the current node (
curr

) to the previous node (
prev

).
Hold the next node temporarily before moving to the child node to avoid losing track of the original next pointer.
Recursively call the function for the child node and link it.
Once the child nodes are processed, continue with processing the temporarily held next node.

Child Pointer Reset :

After processing a node's child list, set
curr.child

to null to ensure no child pointers exist in the final flattened list.

Detailed Steps in Pseudocode

                                            
DEFINE FUNCTION flatten(head):
    # If the head is null, return it as it is
    IF head IS NULL:
        RETURN head
    
    # Create a pseudo head node for easy manipulation
    SET pseudo_head TO NEW Node(0, NULL, head, NULL)
    
    # Initiate the depth-first search with pseudo_head and head
    CALL flatten_dfs(pseudo_head, head)
    
    # Detach the pseudo head from the real head
    SET pseudo_head.next.prev TO NULL
    
    # Return the new head of the flattened list
    RETURN pseudo_head.next

# Helper function to perform depth-first search for flattening the list
DEFINE FUNCTION flatten_dfs(prev, curr):
    # If current node is null, return previous node
    IF curr IS NULL:
        RETURN prev
    
    # Link current node to the previous node
    SET curr.prev TO prev
    SET prev.next TO curr
    
    # Store the next node temporarily
    SET temp_next TO curr.next
    
    # Recursively flatten the child list
    SET tail TO flatten_dfs(curr, curr.child)
    curr.child TO NULL  # After flattening, set child to null
    
    # Recursively flatten the next list and return the tail node
    RETURN flatten_dfs(tail, temp_next)

This approach ensures that the entire multilevel doubly linked list is visited thoroughly and converted into a single-level doubly linked list as required, meeting all constraints given in the problem.