x*****0
发帖数: 452 | 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 | l*****a
发帖数: 14598 | 2 please read PIE
level,
【在 x*****0 的大作中提到】
: 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
| p*****p
发帖数: 379 | 3 给个这个例子应该的结果
是4, 20, 13, 17, 6算一层还是前三个一组后两个一组？
另外tail名字误导人…… | x*****0
发帖数: 452 | 4 thanks, got it.
PIE ==> programming interview exposed?
【在 l*****a 的大作中提到】
: please read PIE
:
: level,
| x*****0
发帖数: 452 | 5 4, 20, 13, 17, 6 一层
【在 p*****p 的大作中提到】
: 给个这个例子应该的结果
: 是4, 20, 13, 17, 6算一层还是前三个一组后两个一组？
: 另外tail名字误导人……
|
|
