Amazon Question: Flatten a multilevel linked list

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:

1. Take "curr" pointer pointing to head of the list.
2. Take "tail" pointer pointing to end of the first level of the list
3. Repeat the following steps until curr != tail
1. if curr has child then:
• Append this child to the tail
• Make the tail points to the end of this child's list.
2. 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)