// 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);
}
