Flatten a multilevel linked list Given such a structure the output should be
  
  
10-&gt;5-&gt;12-&gt;7-&gt;11-&gt;4-&gt;20-&gt;13-&gt;17-&gt;6-&gt;2-&gt;16-&gt;9-&gt;8-&gt;3-&gt;19-&gt;15.

  
  
  Given a linked list where in addition to the next pointer, each node
  has a child pointer, which may or may not point to a separate list.
  These child lists may have one or more children of their own, and so
  on, to produce a multilevel data structure, as shown in below
  figure.You are given the head of the first level of the list. Flatten
  the list so that all the nodes appear in a single-level linked list.
  You need to flatten the list in way that all nodes at first level
  should come first, then nodes of second level, and so on.


This question is attributed to GeekForGeeks. Looking for code-review, optimizations and best practices. Verifying complexity to be \$O(n)\$, where \$n\$ is the count of all the nodes in the input multilevel linked list.

class Nodes&lt;T&gt; {
    Nodes&lt;T&gt; right;
    T item;
    Nodes&lt;T&gt; down;

    Nodes(T item) {
        this.item = item;
    }
}

public final class FlattenMultiLevelList&lt;T&gt; {


    public static &lt;T&gt; List&lt;T&gt; flatten (Nodes&lt;T&gt; node) {
        final List&lt;T&gt; flattenedList = new ArrayList&lt;&gt;();
        final Queue&lt;Nodes&lt;T&gt;&gt; nodeHead = new LinkedList&lt;&gt;();
        nodeHead.add(node);

        // travese the all heads
        while (!nodeHead.isEmpty()) {
            Nodes&lt;T&gt; currNode = nodeHead.poll();
            // traverse all Linkedlists
            while (currNode != null) {
                if (currNode.down != null) { nodeHead.add(currNode.down);  } 

                flattenedList.add(currNode.item);
                currNode = currNode.right;
            }
        }

        return flattenedList;
    }
}

public class FlattenMultiLevelListTest {

    @Test
    public void test() {
        // level 1 should contain only a single linkedlist.
        Nodes&lt;Integer&gt; node1_1_1 = new Nodes&lt;&gt;(10);
        Nodes&lt;Integer&gt; node1_1_2 = new Nodes&lt;&gt;(5);
        Nodes&lt;Integer&gt; node1_1_3 = new Nodes&lt;&gt;(12);
        Nodes&lt;Integer&gt; node14 = new Nodes&lt;&gt;(7);
        Nodes&lt;Integer&gt; node15 = new Nodes&lt;&gt;(11);

        node1_1_1.right = node1_1_2;
        node1_1_2.right = node1_1_3;
        node1_1_3.right = node14;
        node14.right = node15;

        // level 2, first linkedlist, first node
        Nodes&lt;Integer&gt; node2_1_1 = new Nodes&lt;&gt;(4);
        Nodes&lt;Integer&gt; node2_1_2 = new Nodes&lt;&gt;(20);
        Nodes&lt;Integer&gt; node2_1_3 = new Nodes&lt;&gt;(13);

        node2_1_1.right = node2_1_2;
        node2_1_2.right = node2_1_3;
        node1_1_1.down = node2_1_1;

        // level 2, second linkedlist, first node.
        Nodes&lt;Integer&gt; node2_2_1 = new Nodes&lt;&gt;(17);
        Nodes&lt;Integer&gt; node2_2_2 = new Nodes&lt;&gt;(6);
        node2_2_1.right = node2_2_2;
        node1_1_3.down = node2_2_1;


        Nodes&lt;Integer&gt; node3_1_1 = new Nodes&lt;&gt;(2);
        node2_1_2.down = node3_1_1;

        Nodes&lt;Integer&gt; node3_2_1 = new Nodes&lt;&gt;(16);
        node2_1_3.down = node3_2_1;

        Nodes&lt;Integer&gt; node3_3_1 = new Nodes&lt;&gt;(9);
        Nodes&lt;Integer&gt; node3_3_2 = new Nodes&lt;&gt;(8);
        node3_3_1.right = node3_3_2;
        node2_2_1.down = node3_3_1;

        Nodes&lt;Integer&gt; node4_1_1 = new Nodes&lt;&gt;(3);
        node3_2_1.down = node4_1_1;


        Nodes&lt;Integer&gt; node4_2_1 = new Nodes&lt;&gt;(19);
        Nodes&lt;Integer&gt; node4_2_2 = new Nodes&lt;&gt;(15);
        node4_2_1.right = node4_2_2;
        node3_3_1.down = node4_2_1;


        assertEquals(Arrays.asList(10,5,12,7,11,4,20,13,17,6,2,16,9,8,3,19,15), FlattenMultiLevelList.flatten(node1_1_1));
    }

}
What you have here is a right-only in order traversal of your "tree". This means you will have to FIFO-Queue the discovered down nodes to continue from, when you can't traverse right anymore.

Your code nicely reflects this, but I have some comments, especially concerning style and naming:


if (currNode.down != null) { nodeHead.add(currNode.down);  } 



IMO you put too much in this line at once, especially when your currNode cannot be nicely read out loud. 

I do this as a sanity check for my variable names:
read them out loud, when you can't the name is gruesome,
when it sounds silly, the name is bad,
and only when you can read your complete variable name, without sounding Czech, your names are good.

In accordance to that "policy" I'd rename currNode to currentNode or even better traversalNode.

Something similar goes for your nodeHead. I set as a goal for myself: 


  If anybody (not even programmer) can read the name, and instantly tell what the variable, class, interface [...] does, it's good. If a programmer can read the name and instantly tell, it's acceptable, all other names are subject to renaming.


If you hadn't provided the nice graphic, I'd have no clue what nodeHead does.
I'd rename to remainingTraversalHeads or something similar.

Additionally to already made points I personally prefer having blocks separate.
The code from above becomes:

if (traversalNode.down != null) {
    remainingTraversalHeads.add(traversalNode.down);
}


With just these two renames, a little styling and the comments removed, your flatten method becomes:

public static &lt;T&gt; List&lt;T&gt; flatten(Nodes&lt;T&gt; node) {
    final List&lt;T&gt; flattenedList = new ArrayList&lt;&gt;();
    final Queue&lt;T&gt; remainingTraversalHeads = new LinkedList&lt;&gt;();
    remainingTraversalHeads.add(node);

    while (!remainingTraversalHeads.isEmpty()) {
        Nodes&lt;T&gt; traversalNode = remainingTraversalHeads.poll();
        while (traversalNode != null) {
            if (traversalNode.down != null) {
                 remainingTraversalHeads.add(traversalNode.down);
            }
            flattenedList.add(traversalNode.item);
            traversalNode = traversalNode.right;
        }
    }
    return flattenedList;
}


This code IMO is more obvious in it's intention and behaviour.

If I got it right, then this is in fact \$O(n)\$ complexity.