Description: You are given a linked list where every node represents a linked list and contains two pointers of  type:

(a) Pointer to next node in the main list (or the ‘right’ pointer)
(b) Pointer to a linked list where this node is head (or ‘down’ pointer).
All linked lists are sorted.

Write a function flatten() to flatten the lists into a single linked list.

 

If video does not load, Click here

Algorithm:

We study two recursive functions flatten(root) and merge( a,b )to solve the problem 

Flatten(root)

•       If root== Null or root->right is null, return

•       Else Merge this list with the list on right side by calling merge(root , flatten(root->right)) and return the merged pointer. 

Merge( a,b )

•        Uses the merge procedure to merge two linked lists pointed by a and b and returns a pointer to sorted linked list.

C Implementation

 
/* A Linked List Node */
typedef struct Node
{
    int data;
    struct Node *right;
    struct Node *down;
} Node;
 
/* Function to merge two sorted linked lists */
Node* merge( Node* a, Node* b )
{
    /* If first list is empty, the second list is returned */
    if(a == NULL)
        return b;
    /* If second list is empty, the first list is returned */
    if(b == NULL)
        return a;
    /* Compare the data elements of head nodes of both lists
        and put the smaller one in result thus merging the two lists*/
 
   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;
}
 
/* Function that flattens a given linked list */
Node* flatten (Node* root)
{
    /* Base cases */
    if( root == NULL || root->right == NULL )
        return root;
    /* Merge this list with the list on right side */
    return merge( root, flatten(root->right) );
}
Go to top