w******g
发帖数: 189 | 1 就是那道双向链表题：
"
一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
一个链表。要求把它拍扁，顺序随意。
"
题目确切是啥意思？有没有大牛讲讲或者举个例子？解题思路呢？
thanks in advance! |
l*****a
发帖数: 14598 | 2 PIE中有类似的题吧
【在 w******g 的大作中提到】
: 就是那道双向链表题：
: "
: 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
: 一个链表。要求把它拍扁，顺序随意。
: "
: 题目确切是啥意思？有没有大牛讲讲或者举个例子？解题思路呢？
: thanks in advance!
|
w******g
发帖数: 189 | |
f******n
发帖数: 279 | |
w******g
发帖数: 189 | 5 就是那道双向链表题：
"
一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
一个链表。要求把它拍扁，顺序随意。
"
题目确切是啥意思？有没有大牛讲讲或者举个例子？解题思路呢？
thanks in advance! |
l*****a
发帖数: 14598 | 6 PIE中有类似的题吧
【在 w******g 的大作中提到】
: 就是那道双向链表题：
: "
: 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
: 一个链表。要求把它拍扁，顺序随意。
: "
: 题目确切是啥意思？有没有大牛讲讲或者举个例子？解题思路呢？
: thanks in advance!
|
w******g
发帖数: 189 | |
f******n
发帖数: 279 | |
f**********t
发帖数: 1001 | 9 // Given a doubly linked list with a data item, a previous and a next ptr
along with another pointer "child" that may point to the head of another
doubly linked list of same type(it will lead to a general tree type of
structure) or it may be null. Flatten the tree into a linked list... minimum
space and time complexity(order n). The doubly linked lists's head and tail
are given.
struct List;
struct ListNode {
char val;
ListNode *pre, *next;
List *child;
};
struct List {
ListNode *head, *tail;
List(ListNode *h, ListNode *t) : head(h), tail(t) { }
};
List FlatList(List &li) {
if (li.tail == nullptr) {
return li;
}
ListNode *newtail = li.tail;
for (ListNode *p = li.head; p != li.tail; p = p->next) {
if (p->child != nullptr) {
List cur = FlatList(*(p->child));
if (cur.tail == nullptr) {
continue;
}
newtail->next = cur.head;
cur.head->pre = newtail;
newtail = cur.tail;
}
}
return List(li.head, newtail);
} |
