m******n
发帖数: 51 | 1 看了之前大家的分享 大部分题都有命中 除了这题 分享给大家 之后面的人记得准备
题目跟这题类似
https://sites.google.com/site/spaceofjameschen/home/linked-list/flatten-and-
deflatten-doubly-linked
只是NEXT改成 上下(UP and Down)都可
class Node
{
int data;
Node Prev;
Node Next;
Node Up;
Node Down;
}
Another easier 类似题.
http://www.geeksforgeeks.org/flatten-a-linked-list-with-next-an |
t*******e
发帖数: 274 | 2 up和down具体怎么处理？up node都往head前面放？down node都往tail后面放？ |
s*******n
发帖数: 305 | 3 谢谢楼主分享面经
1. 是up->down->tail 还是tail->up->down.
2. 看楼主第一个分享的链接， 还有de_faltten, 尿了， 这个是个啥意思， 恢复成原
来的样子？ 可是解不唯一呀？ |
s*******n
发帖数: 305 | 4 谢谢楼主分享面经
1. 是up->down->tail 还是tail->up->down.
2. 看楼主第一个分享的链接， 还有de_faltten, 尿了， 这个是个啥意思， 恢复成原
来的样子？ 可是解不唯一呀？ |
v**N
发帖数: 11 | |
f********y
发帖数: 156 | 6 貌似 tail->up -> down。其实up / down 可以交换，你在flatten的时候先处理谁，那
么在unflatten也要先处理它。
Deflatten的唯一是因为 up / down 指针在flatten以后还保留着。flatten 只是把上
下层的表头连到了当前层的尾巴。
Deflatten的时候，觉得应该BFS。 貌似分层的问题，染色的问题，都是BFS。（ 楼主
原帖里的link 中有个递归做deflatten的函数，感觉不大对）
void deflatten(Node* pHead) {
if(! pHead ) {
return;
}
queue q;
q.push(pHead);
while(!q.empty()) {
Node* p = q.front();
q.pop();
while(p) {
if(p->up) {
p->up->prev->next = nullptr;
p->up->prev = nullptr;
q.push(p->up);
}
if(p->down) {
p->down->prev->next = nullptr;
p->down->prev = nullptr;
q.push(p->down);
}
p = p->next;
}
}
}
【在 s*******n 的大作中提到】
: 谢谢楼主分享面经
: 1. 是up->down->tail 还是tail->up->down.
: 2. 看楼主第一个分享的链接， 还有de_faltten, 尿了， 这个是个啥意思， 恢复成原
: 来的样子？ 可是解不唯一呀？
|
g*******n
发帖数: 214 | 7 请问up/down之后一定是head么？还是有可能有prev。 |
m******n
发帖数: 51 | 8 It is a little bit similar to Leetcode
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
but flatten a four-direction node graph to doubled linked list
and
1. No extra memory should be used
2. Node order doesn't matter
【在 s*******n 的大作中提到】
: 谢谢楼主分享面经
: 1. 是up->down->tail 还是tail->up->down.
: 2. 看楼主第一个分享的链接， 还有de_faltten, 尿了， 这个是个啥意思， 恢复成原
: 来的样子？ 可是解不唯一呀？
|
m******n
发帖数: 51 | 9
【在 m******n 的大作中提到】
: It is a little bit similar to Leetcode
: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
: but flatten a four-direction node graph to doubled linked list
: and
: 1. No extra memory should be used
: 2. Node order doesn't matter
|
m******n
发帖数: 51 | 10 Remember to handle node 2 and Node 5 case which moving Node 5 behind Node 3. |
s*******n
发帖数: 305 | 11 谢谢楼主的详细分析， good luck with your linkedin |
E******g
发帖数: 204 | 12 楼主好人， 祝拿到offer！
and-
【在 m******n 的大作中提到】
: 看了之前大家的分享 大部分题都有命中 除了这题 分享给大家 之后面的人记得准备
: 题目跟这题类似
: https://sites.google.com/site/spaceofjameschen/home/linked-list/flatten-and-
: deflatten-doubly-linked
: 只是NEXT改成 上下(UP and Down)都可
: class Node
: {
: int data;
: Node Prev;
: Node Next;
|
