## Algorithmathon Day 8: Double Linked List Unflattening

Created: 22 July 2013  Modified:

On Day 8 we will be unflattening the Double Linked List (DoLL) that we flattened on Day 7 of the Algorithmathon. As always we will be following the Rules of Algorithmathon. For your viewing pleasure the source code is also available. How do we go about achieving this unflattening? It seems likely, what we need to do is to reverse the flattening process.

We should be able to reuse our test that verified our helper methods to help us write our first test.

To try to grasp how we might solve this problem we can list out the rules we used for flattening the list.

• Starting at the head check each element for a child
• If the element has a child
• link the child elements into the top list.
• Return to step 1 with the child list’s first element as a target.
• Continue to the next element. (Which will be the first element in the child list if one existed)

What needs to be done to reverse this process? Well we should probably start at the beginning much like the flattening process.

• Starting at the head check each element for a child
• If the element has a child
• unlink the child elements from the top list.
• Return to step 1 with the child list’s first element as a target.
• Continue to the next element. (Which will be the element after the last element in the child list if one existed)

While it sounds correct this plan will prove ultimately futile. When we flattened our list we started at the bottom and worked our way up. If we reverse this process we need to start at the top and work our way down. It would look something more like this.

• Starting at the head check each element for a child
• If the element has a child goto step 1 with the child’s first element as a target.
• Make the elements next node equal to the next node of the last element of the child list.
• Continue to the next element. (Which will be the element after the last element in the child list if one existed)

In this case the code seems easier to understand than the aforementioned steps.