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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这里的父子节点指向的是任意链表吗?有没有可能是原链表中的节点?
|
s**x 发帖数: 7506 | 6
去除child pointer. 我有本面试书有这道题,倒是没提父指针。
也可以简单的把父指针清空。
【在 M********6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 什么叫拍扁?去除父指针?
|
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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是不是每个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 这个是不是假设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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 贴一个以作参考: : DLNode * flatten_list(DLNode *head) : { : DLNode *p, *phead, *ptail; : p = head; : while(p->next){ : p = p->next; : } : phead = head; : ptail = p;
|