# List Flattening and Unflattening

FLATTENING LIST PROBLEM: Start with a standard doubly linked list. Now imagine that in addition

to the next and previous pointers, each element has 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 figure below:

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You

are given the head and tail of the first level of the list. Each node is a C struct

with the following definition:

```
typedef struct Node {
struct Node *next;
struct Node *prev;
struct Node *child;
int value;
} Node;
```

SOLUTION:

```
bool listFlattening(Node *head, Node **tail) {
if(head == NULL) return true;
Node *temp = head;
while(temp != NULL) {
if(temp->child != NULL) {
(*tail)->next = temp.child;
temp->child->prev = tail;
*tail = temp->child;
while((*tail)->next != NULL) *tail = (*tail)->next;
}
temp = temp->next;
}
}
```

*I haven’t run this solution to make sure it works. But the idea should be good.

UNFLATTENING PROBLEM: Unflatten the list created by the previous problem and restore the

data structure to its original condition.

SOLUTION:

```
void listUnflatten(Node *head, Node **tail) {
Node *temp = head;
while(temp != NULL) {
if(temp->child && temp->child->prev != NULL) {
Node *child = temp->child;
child->prev->next = NULL;
child->prev = NULL;
listUnflatten(child, tail);
}
temp = temp.next;
//TODO: update tail here.
}
```