Flattening a doubly linked list

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

You could write this code in Java first, it would not be much different from a C++ implementation. It seems that your problem is not the language, but rather the algorithm: E.g. you only update the next pointer, not the prev pointer. The following must be true for every link between two nodes: node->next->prev == node.

Let me try to answer your questions:

-
The "doubly" part is not required to write something that can be flattened, but it is explicitly asked for so you must maintain it. It will allow you to traverse the list in two directions, instead of just one. This can be valuable in many situations.

-
The question states that the child pointer is to a list similar to the first list. This means that it can also have child pointers of its own. A recursive solution would be easy to write and easy to understand.

-
Why do you want a non-recursive algorithm? This is not stated in the question.

-
I believe you can use any language you like in this forum.

StackExchange Code Review Q#2536, answer score: 4