**Problem:**Given a linked list where in addition to the next pointer, each node has a child pointer, which may or may not point to a separate list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure. You are given the head of the first level of the list. Flatten the list so that all the nodes appear in a single-level linked list. Flatten the list in way that all nodes at first level should come first, then nodes of second level, and so on.

**Solution:**

Follow the following steps:

- Take "curr" pointer pointing to head of the list.
- Take "tail" pointer pointing to end of the first level of the list
- Repeat the following steps until curr != tail
- if curr has child then:
- Append this child to the tail
- Make the tail points to the end of this child's list.
- Assign curr->next to curr.

**Implementation:**

//Structure of the node

struct Node

{

Node *next;

Node *child;

int data;

Node(int d, Node* n = 0, Node* c = 0):data(d), next(n), child(c){}

};

void ListWithChild::flattenList()

{

if(!head)

return;

Node *tail = head;

while(tail->next)

tail = tail->next;

Node *curr = head;

while(curr != tail)

{

if(curr->child)

{

tail->next = curr->child;

while(tail->next)

tail = tail->next;

}

curr = curr->next;

}

}

**Complexity:**O(n)

## No comments:

## Post a Comment