LINKEDLIST FLATTENING

Start with a standard doubly-linked list. Now imagine that in addition to 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 Figure 4-3.
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;


This algorithm is as follows:
Start at the beginning of the first level
While you are not at the end of the first level
If the current node has a child
  Append the child to the end of the first level
  Update the tail pointer
Advance to next node


The code for this algorithm is as follows:

void flattenList( Node *head, Node **tail)
Node *curNode =  head;
while( curNode ){
/* The current node has a child */
if( curNode->child ){
append( curNode->child, tail );
}
curNode = curNode->next;
}
}

/* Appends the child list to the end of the tail and updates  ;
* the tail.
*/

void append( Node *child, Node **tail ){
Node *curNode;
/* Append the child child list to the end */
(*tail)->next = child;
child->prev = *tail;

/*Find the new tail, which is the end of the child child   ;
*list.
*/

for( curNode = child; curNode->next;
curNode = curNode->next )
; /* Body intentionally empty */
/* Update the tail pointer now that curNode is the new 
* tail.
*/
*tail = curNode;
}