List Flattening from book <interviews exposed... Chapter4># JobHunting - 待字闺中
r*n
1 楼
我的递归解法，大家看看对吗？
Node flat_list_head[N]; // N is the largest level.
void flattenList(Node *head, int level)
{
if (head->next){
insert_node_front_flat_list_head(head, level);
// Go next
head = head->next;
flattenList(head, level);
}
if (head->child){
insert_node_front_flat_list_head(head, level+1);
// Go child
head = head->child;
flattenList(head, level+1);
}
}
void insert_node_front_flat_list_head(Node* node, int level)
{
// Insert the node of head at front end of flat_list_head[level]
node->next = flat_list_node[level]->next;
flat_list_node[level]->next->prev = node;
flat_list_node[level]->next = node;
node->prev = flat_list_node[level];
}
// from book
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;
}
Node flat_list_head[N]; // N is the largest level.
void flattenList(Node *head, int level)
{
if (head->next){
insert_node_front_flat_list_head(head, level);
// Go next
head = head->next;
flattenList(head, level);
}
if (head->child){
insert_node_front_flat_list_head(head, level+1);
// Go child
head = head->child;
flattenList(head, level+1);
}
}
void insert_node_front_flat_list_head(Node* node, int level)
{
// Insert the node of head at front end of flat_list_head[level]
node->next = flat_list_node[level]->next;
flat_list_node[level]->next->prev = node;
flat_list_node[level]->next = node;
node->prev = flat_list_node[level];
}
// from book
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;
}