[Amazon][GFG] Flattening a Linked List

Problem: Given a Linked List of size N, where every node represents a sub-linked-list and contains two pointers:

1. a next pointer to the next node,
2. a bottom pointer to a linked list where this node is head.

Each of the sub-linked-list is in sorted order.

Flatten the Link List such that all the nodes appear in a single level while maintaining the sorted order. 

Note: The flattened list will be printed using the bottom pointer instead of the next pointer.

Example:

Input:
5 -> 10 -> 19 -> 28
|     |     |     | 
7     20    22   35
|           |     | 
8          50    40
|                 | 
30               45
Output:  5-> 7-> 8- > 10 -> 19-> 20->
22-> 28-> 30-> 35-> 40-> 45-> 50.
Explanation:
The resultant linked lists has every 
node in a single level.
(Note: | represents the bottom pointer.)

Input:
5 -> 10 -> 19 -> 28
|          |                
7          22   
|          |                 
8          50 
|                           
30              
Output: 5->7->8->10->19->22->28->30->50
Explanation:
The resultant linked lists has every
node in a single level.

(Note: | represents the bottom pointer.)

Approach: We can treat every node as separate list where next pointer is bottom pointer. Now this will just become the problem of merging sorted lists.

That's all!

Implementation in Java:

    Node flatten(Node root)

    {

    if (root == null || root.next == null)

    {

        return root;

    }

    root.next = flatten(root.next);

    return merge(root, root.next);

    }

    

    private Node merge(Node node1, Node node2)

    {

        if (node1 == null)

        {

            return node2;

        }

        if (node2 == null)

        {

            return node1;

        }

        Node result = null;

        if (node1.data <= node2.data)

        {

            result = node1;

            result.bottom = merge(node1.bottom, node2);

        }

        else

        {

            result = node2;

            result.bottom = merge(node1, node2.bottom);

        }

        result.next = null;

        return result;

    }

Complexity: O(n) where n is total number of nodes in the list including the bottom nodes.