Friday, June 12, 2015

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.


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.


//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()

Node *tail = head;
tail = tail->next;

Node *curr = head;
while(curr != tail)
tail->next = curr->child;
tail = tail->next;

curr = curr->next;

Complexity: O(n)

No comments:

Post a Comment