Flatten a multi level DLL

Similar copy list problem with random pointer, there is a DLL with child pointers. Some nodes have non-null child pointer. So problem is to create a single DLL with merging the child lists.

This is not a complex problem. I think many can guess that this problem can be solved using recursion.
This can be solved in 3 ways:

  • in a while go over list till not None. In a loop if a node is having a child pointer, call the same function recursively by passing child pointer.
  • In a recursive function, check if a node is NULL return. add the node to the new list, if the node is having child pointer, call it recursively. if a node having next pointer call it recursively.
  • This solution I learnt from solutions approach. This solution uses the stack pointer. Push the head. In a while loop pop the node from the stack and add it to newlist. If a node has next pointer push it. If a node child pointer push it. Note stack is LIFO. As child pointer should be processed before next pointer, we should push child pointer last.

Below is the code for approach 2:

stack based solution:

In Python, I dont know if a variable is assigned to another pointer pointer variable, does the new variable point to the existing address or it does copy memory.

Please give your comments.




Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store