In this **Leetcode Flatten a Multilevel Doubly Linked List problem solution** 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 example below.

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.

## Problem solution in Python.

class Solution: def flatten(self, head: 'Node') -> 'Node': def helper(head, stack=[]): if not head: return head node = head while node: if node.child: if node.next: stack.append(node.next) temp = node.child node.next = temp temp.prev = node node.child = None elif not node.next and stack: temp = stack.pop() node.next = temp temp.prev = node node = node.next return head return helper(head)

## Problem solution in Java.

class Solution { public Node flatten(Node head) { Node refHead = head; while (refHead != null) { Node next = refHead.next; Node child = flatten(refHead.child); Node childRef = child; while (child != null && child.next != null) { child = child.next; } if (childRef != null) { refHead.child = null; refHead.next = childRef; childRef.prev = refHead; child.next = next; if (next != null) { next.prev = child; } } refHead = next; } return head; } }

## Problem solution in C++.

class Solution { public: Node* flatten(Node* head) { flattenEnd(head); return head; } Node *flattenEnd(Node *head) { if (!head) return head; Node *fp = head, *next; while (fp) { next = fp->next; if (fp->child) { Node *end = flattenEnd(fp->child); fp->next = fp->child; fp->next->prev = fp; fp->child = NULL; fp = end; fp->next = next; if(next) next->prev = end; } if (!next) break; fp = next; } return fp; } };

## 0 Comments