Flatten a Multilevel Linked List (Pointer Reconnection)

Problem: Flatten a Multilevel Linked List You are given a multilevel linked list. Each node has a next pointer and an additional pointer child that may point to the head of a sub-list. A non-null child indicates a downward list starting from that node. Flatten the list into a single-level linked list in DFS pre-order: Traverse the main list from head to tail. When you encounter a node x with x.child != null, splice the child list between x and x.next. After the entire child list is flattened, continue with the original x.next (which you should have saved before splicing). After flattening, all child pointers must be set to null. Function Signature Implement flatten(head) and return the head of the flattened list. Example (structure) Main list: 1 -> 2 -> 3 -> 4 2.child points to: 7 -> 8 8.child points to: 11 -> 12 Flattened result: 1 -> 2 -> 7 -> 8 -> 11 -> 12 -> 3 -> 4 Constraints Number of nodes N: 0 <= N <= 10^4 Target time complexity: O(N) Recursion or iteration is allowed; if using recursion, be mindful of worst-case depth up to N. What to get right How to obtain the tail of the flattened child segment. How to reconnect that tail back to the saved original next node without breaking the list. Example Input [multilevel list: 1->2->3->4, 2.child=7->8, 8.child=11->12] Output 1 2 7 8 11 12 3 4