Flattening a doubly linked list

Question

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).

Answer 1

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.

Answer 2

if(!head||!tail) return;

Should it really happen that head or tail can be null? Is it really right to ignore a situation head is null and tail isn't? I'm suspicious of what this test is doing.

Don't do this:

while(!head->down &&!(head==tail))

Do this:

while(!head->down && head != tail)

Less symbols makes its easier to read the code.

As for the algorithm:

In order to implement the iterative algorithm you need the doubly-linked lists. i.e. by ignoring those you've made yourself unable to find the non-recursive algorithm.

Since you want to practice for an interview, I'm rot13ing the following hints, so you can use as much or as little as you want:

1. Guvax guebhtu n cebprff bs jevgvat n shapgvba gung sbyybjf gur hasynggrarq punva jvgubhg synggravat vg. Gura nqq synggravat gb gung cebprff.
2. Ng rnpu abqr lbh pna znxr bar bs guerr pubvprf: Zbir Arkg, Zbir Qbja, Zbir Onpx Hc.
3. Jura lbh zbir qbja, gur cerivbhf cbvagre ba gur abqr jvyy or hahfrq. Frg gung cbvagre fb lbh pna pbzr onpx gb gur cerivbhf yriry.
4. Zbivat hc vf gevpxl, ohg lbh fubhyq xabj gur gnvy naq urnq bs gur ybjre yvfg nf jryy nf gur abqr sebz juvpu lbh npprffrq gur ybjre yvfg. Pnershyyl zbir gubfr cbvagref nebhaq!