一道面试题：Flatten a multilevel linked list# JobHunting - 待字闺中
x*0
1 楼
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, as shown in below figure.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. You need to flatten the list in way
that all nodes at first level should come first, then nodes of second level,
and so on.
Each node is a C struct with the following definition.
struct list
{
int data;
struct list *next;
struct list *child;
};
My idea:
BFS. When encountering a child, push it to a queue. After traversal the
first level, pop an element from the queue and link the last element of the
first level to the popped element.
The following is my code:
void flattenList(struct node *head)
{
struct node* cur = head;
struct node* tail = NULL;
struct node* temp = NULL;
queue q;
while(!q.empty() || cur != NULL)
{
if(cur != NULL)
{
if(!q.empty())
{
temp = q.front();
if(temp == cur)
{
q.pop();
}
}
if(cur->child != NULL)
{
q.push(cur->child);
}
tail = cur;
cur = cur->next;
}
else
{
if(!q.empty())
{
temp = q.front();
q.pop();
tail->next = temp;
cur = tail->next;
}
}
}
}
For the given example:
1 level:10, 5, 12, 7, 11
2 level: 4, 20,13, 17,16
Can anyone help me verify my algorithm?
And really appreciate provide another solution?
Thanks,
Zhong
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, as shown in below figure.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. You need to flatten the list in way
that all nodes at first level should come first, then nodes of second level,
and so on.
Each node is a C struct with the following definition.
struct list
{
int data;
struct list *next;
struct list *child;
};
My idea:
BFS. When encountering a child, push it to a queue. After traversal the
first level, pop an element from the queue and link the last element of the
first level to the popped element.
The following is my code:
void flattenList(struct node *head)
{
struct node* cur = head;
struct node* tail = NULL;
struct node* temp = NULL;
queue
while(!q.empty() || cur != NULL)
{
if(cur != NULL)
{
if(!q.empty())
{
temp = q.front();
if(temp == cur)
{
q.pop();
}
}
if(cur->child != NULL)
{
q.push(cur->child);
}
tail = cur;
cur = cur->next;
}
else
{
if(!q.empty())
{
temp = q.front();
q.pop();
tail->next = temp;
cur = tail->next;
}
}
}
}
For the given example:
1 level:10, 5, 12, 7, 11
2 level: 4, 20,13, 17,16
Can anyone help me verify my algorithm?
And really appreciate provide another solution?
Thanks,
Zhong
