# Flatten a multi-level linked list

• Given a linked list with both next and down pointers, flatten the list into a single linked list.
For example, given

``````A---B---C----D--E---F--NULL
|
G---H---I---J--NULL
|
K---L--NULL
``````

should become A-B-C-G-H-K-L-I-J-D-E-F-NULL

• @ankanr Is it possible some of the inner modes to have down pointers or only the first nodes posess this property? How many levels comprise the list ?
Was there a contraint on the number nodes in each level?

Also what happens in the following example : ?

``````
A---B----C---D---E----F---S--M---N
|
G---H---I----J---NULL
|
K--L--P--NULL
|
S--T--NULL``````

• any node can have down pointer, including the inner node.

also, the down pointer can be valid or null. similarly the next pointer can be valid or null.

in you case, the solution becomes

A-G-K-S-T-L-P-H-I-J-B-C-D-E-F-S-M-N-NULL

• @ankankr Thank you very much! Just another question : Do you think your example is correct?
In your example you iterate a part of the first level of the list (A,B,C) , but in my example you iterate in deep A-G-K-S, something like dfs
Isn't the answer of the given example :
A-G-K-L-H-I-J-B-C-D-E-F
Can you calrify the rule of list flattening?

Given a linked list with both next and down pointers, flatten the list into a single linked list.
For example, given
A---B---C----D--E---F--NULL
|
G---H---I---J--NULL
|
K---L--NULL

should become A-B-C-G-H-K-L-I-J-D-E-F-NULL

• @elmirap I agree with you.

• Thanks for pointing out. My example is incorrect because of formatting issue. I intended to have down pointer from C in the first level, then H in the second level, but it did not show up correctly when posted. Hope that clarifies.

• @ankankr You can edit your original post to fix the issues.

• @babhishek21 This is the original example.

`````` A---B---C----D--E---F--NULL
|
G---H---I---J--NULL
|
K---L--NULL

should become A-B-C-G-H-K-L-I-J-D-E-F-NULL``````

• @elmirap So how does one establish which node comes first in the flattening? (:yum:)
For the example

`````` A---B---C----D--E---F--NULL
|
G---H---I---J--NULL
|
K---L--NULL

should become A-B-C-G-H-K-L-I-J-D-E-F-NULL
``````

it looks like that once we reach the lowest/deepest level, the nodes of a deeper level will always hold priority over nodes of a shallower level. Am I right in thinking so?

• @babhishek21 yes, I think the same. We traverse the list taking always the down link first .If down list doesn't exist we will move to the right

• @ankankr What will be the result of this input? Thank you

`````` A---B---C---D--E---F--NULL
|   |
G---H---I---J--NULL
|   |
K---L--NULL``````

• I think the idea is to simply do a DFS with the down pointer begin processed first.

@1337c0d3r @elmirap Do you think this question is worthy of being published?

• @babhishek21 Yes definitely. This is a classic problem, would love to add it to the library. Let's communicate via chat.

• I think this problem is similar to (maybe the same as) pre-order traversal of binary tree.

• This is version of the pseudocode i would use to solve the problem

``````class Node():
def __init__():
self.val=-1
self.next=None
self.down=None

stack=[]
dummy=new Node()
else:
if(len(stack)!=0):
return dummy.next``````

• @elmirap I am also curious about the case when input multi-level linked list has multiple down pointers referencing the lower level. But I guess in this case, only the first down pointer is useful as it has to point to the head of the lower level list. If this is the case, then having multiple down pointers at the same level only adds complexity to the logic in the code, I think. Anyway, it will need a good definition of what flatten means to well form a good problem.

• Assuming the desired flattened liked list is to always move lower level list up right after bifurcation node, and attach the remaining list after the flattened link, then we can do DFS to locate bifurcation node on each level and modify its next pointer to point to the flattened list of lower level. Finally, we need to set down pointer in each node to `NULL` since the returned list must be flattened.

``````struct Node { // define multi-level linked list node
Node* next, *down;
Node():next(NULL), down(NULL) { }
};

while (cur && !cur->down) cur = cur->next; // find bifurcation node
if (!cur) return head; // if no bifurcation, just return
Node* nxt = cur->next; // record the remaining list after bifurcation node
cur->next = flatten(cur->down); // flatten lower level list
cur->down = NULL; // flatten bifurcation node
while (cur->next) {  // find the new tail after flatten and set down to NULL
cur->down = NULL;
cur = cur->next;
}
cur->next = nxt; // attach tail to the remaining list
}
``````

• flatten(cur->down)

cur->next=nxt will not work.
You should flatten nxt!

• ``````/*
class ListNode {
int val;
ListNode next;
ListNode down;
ListNode(int val) {
this.val = val;
}
}
/*
* My Java solution using recursion and DFS
* I simply assume there is only one node in the upper level who can get access to the lower level.
* If not, you can simply add a flag to detect whether the lower level is been flattened or not.
*/
while (running != null) {
if (running.down != null) {
ListNode next = running.next;
ListNode fromBellow = flattenList(running.down);
running.next = fromBellow;
running.down = null;
while (running.next != null) {
running = running.next;
}
running.next = next;
}
if (running.next != null) {
running = running.next;
} else {
break;
}
}
}``````

• @ankankr Pardon me if I got it wrong. Based on your examples, the problem looks equivalent to pre-order traversal of the list to me. Correct me if I am mistaken.

``````// Class to represent a node
class Node{
char data;
Node next, down;

public Node(char data) {
this.data = data;
this.next = null;
this.down = null;
}
}

// Method to flatten the list
return "";

// Below lines are written in this manner to increase the code readability.
// One may choose to use StringBuilder instead of String to optimize it.
String result = "";
result += head.data + " ";