I am a Java dev and trying to prepare for interviews in C++. Can someone please review the below solution for me?
Assume that you are given the head and tail pointers of a doubly linked list where each node can also have a single child pointer to another similar doubly linked list. There are no cycles in this structure outside of the traditional double links. Write a procedure in C++ that flattens this structure into a single list.
**I am ignoring that it is a doubly linked list for now to make the posted code more simple, since the "doubly" part doesn't seem to be of any help to me for this question.
void LL::flatten(Node *head,Node *tail)
{
if(!head||!tail) return;
while(!head->down &&!(head==tail))
{
head = head->next;
}
// Flattening is complete
if(head==tail && !head->down) return;
tail->next = head->down;
head->down = null;
//getTail returns the last node of the linkedlist
flatten(head->next, getTail(tail->next));
}
class Node
{
public:
Node()
{
next = prev = down = null;
data = -1;
}
private:
Node * next;
Node * down;
Node * prev;
int data;
};
I have some questions:
- Is the "doubly" part required. What am I missing?
- I have read it is better non-recursively. How is that? Since we have only pointers on the stack and the actual objects/list structure are on the heap, this should not take huge space on the stack, apart from usual recursion overheads.
- Does someone have a non-recursive way of doing it in C++ or Java. The code on this forum is in C# and I am having trouble understanding it with enumerations and all the iterations
- The
getTail(tail->next)
function is \$O(n)\$. Is there a way of not using this function ?. Even If I attach the 'down' linked list to the next node instead of last node, I will need the last node of the 'down' LL so that I can attach it to the next node of parent.
Though I know there might be many solution already posted elsewhere, I am looking for review for my code as well, this will help me understand my gaps while coding in c++ (at least up to interview standards).