The problem we are exploring is to flatten a singly linked list. The initial singly linked list (to be flattened) has nodes of the following type:

(1) Pointer to next node in the main list (we call it ‘right’ pointer in code)
(2) Pointer to a sorted linked list where this node is head (we call it ‘down’ pointer in code).

Flattening a linked list should generate a linked list with nodes of the following type:

(1) Only one pointer to the next node
(2) All nodes are sorted based on data

For instance: the singly linked list is as follows:


1 -> 5 ->  7 ->  30
|    |     |     |
V    V     V     V
2    11    10    40
|          |     |
V          V     V
6          15    50
|
V
9


After flattening the above linked list, the resultant linked list should be:


1 -> 2 -> 5 -> 6 -> 7 -> 9 -> 10 -> 11 -> 15 -> 30 -> 40 -> 50


### Approach

The approach towards solving this is to use the key idea of:

• Merging in merge sort algorithm

The idea is to use Merge() process of merge sort for linked lists. We use merge() to merge lists one by one. We recursively merge() the current list with already flattened list. The down pointer is used to link nodes of the flattened list.

### Pseudocode


// The merge component of merge sort in Linked List
Node merge(Node a, Node b)
{
if (a == null)     return b;
if (b == null)      return a;
Node result;
if (a.data < b.data)
{
result = a;
result.down =  merge(a.down, b);
}
else
{
result = b;
result.down = merge(a, b.down);
}
return result;
}
// Utility to flatten the linked list
Node flatten(Node root)
{
if (root == null || root.right == null)
return root;
root.right = flatten(root.right);
root = merge(root, root.right);
return root;
}


### Complexity

• Worst case time complexity: Θ(N ^ (2*K))
• Average case time complexity: Θ(N ^ (2*K))
• Best case time complexity: Θ(N ^ 2)
• Space complexity: Θ(1)

where n is the number of down linked lists and k is the average size of the linked lists.

• Java

### Java


{
private class Node
{
int data;
Node right, down;
Node(int d)
{
data = d;
right = null;
down = null;
}
}
Node merge(Node a, Node b)
{
if (a == null)     return b;
if (b == null)      return a;
Node result;
if (a.data < b.data)
{
result = a;
result.down =  merge(a.down, b);
}
else
{
result = b;
result.down = merge(a, b.down);
}
return result;
}
Node flatten(Node root)
{
if (root == null || root.right == null)
return root;
root.right = flatten(root.right);
root = merge(root, root.right);
return root;
}
{
Node new_node = new Node(data);
}
public void print_list()
{
while (temp != null)
{
System.out.print(temp.data+"->");
temp = temp.down;
}
System.out.println("NULL");
}
public static void main(String [] args)
{ 