A*****o
发帖数: 284 | 1 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
一个链表。要求把它拍扁，顺序随意。
请大牛给个指点.谢谢 |
s**x
发帖数: 7506 | 2 父节点不用管吧？
scan each node from head to tail,
if child node is is not null
append child node to the tail
that is it. |
A*****o
发帖数: 284 | 3 这里的父子节点指向的是任意链表吗？有没有可能是原链表中的节点？ |
M********6
发帖数: 67 | |
s**x
发帖数: 7506 | 5
肯定是后者。
【在 A*****o 的大作中提到】
: 这里的父子节点指向的是任意链表吗？有没有可能是原链表中的节点？
|
s**x
发帖数: 7506 | 6
去除child pointer. 我有本面试书有这道题，倒是没提父指针。
也可以简单的把父指针清空。
【在 M********6 的大作中提到】
: 什么叫拍扁？去除父指针？
|
n*******1
发帖数: 145 | 7 我觉得参照leetcode的flattern binary tree吧 感觉是一回事 |
s********f
发帖数: 510 | 8 是不是每个node除了有next之外还有parent和child?
那样的话,保持一个tail指向最后一个节点, 然后从head开始遍历整个list,碰到一个
node有parent(child)就把tail指向parent(child),然后update tail还是指向最后一个
节点.
当遍历结束后,就flatten了. |
g*********e
发帖数: 14401 | 9
这个是不是假设parent/child 是新list的头结点？
【在 s********f 的大作中提到】
: 是不是每个node除了有next之外还有parent和child?
: 那样的话,保持一个tail指向最后一个节点, 然后从head开始遍历整个list,碰到一个
: node有parent(child)就把tail指向parent(child),然后update tail还是指向最后一个
: 节点.
: 当遍历结束后,就flatten了.
|
s********f
发帖数: 510 | 10 是的,要不parent/child所在list的head是无法找到的.
【在 g*********e 的大作中提到】
:
: 这个是不是假设parent/child 是新list的头结点？
|
|
|
w******g
发帖数: 189 | 11 贴一个以作参考：
DLNode * flatten_list(DLNode *head)
{
DLNode *p, *phead, *ptail;
p = head;
while(p->next){
p = p->next;
}
phead = head;
ptail = p;
while(phead->next != NULL){
if(phead->child != NULL){
ptail->next = phead->child;
phead->child->prev = ptail;
while(ptail->next != NULL){
ptail = ptail->next;
}
}
phead = phead->next;
}
return head;
} |
x*****0
发帖数: 452 | |
l**********1
发帖数: 415 | |
x*******9
发帖数: 138 | |
m*****n
发帖数: 2152 | 15 这个解法好像没考虑到有环的情况吧。
1<->2<->3<->4<->5<->6....<->n
其中2<->4<->2互为父子节点。
必须建个hash table，把list里面的node全存下来，当child指到list的node的时候，
stop。
而且新的father child list可能也有环，所有还要建visit table。
【在 w******g 的大作中提到】
: 贴一个以作参考：
: DLNode * flatten_list(DLNode *head)
: {
: DLNode *p, *phead, *ptail;
: p = head;
: while(p->next){
: p = p->next;
: }
: phead = head;
: ptail = p;
|
