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).

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

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