Home » Interview Questions » LinkedList Interview Questions » Flattening a linked list

Flattening a linked list


()

In the given linked list, every node has two pointers :

1. Pointer to next node (Main linked list(right pointer))

2. Pointer to next node where this node is head (Down linked list(down pointer))

We need to flatten this linked list into one normal singly linked list. And the output linked list should be sorted. The down list and right lists should be sorted atready that is right and down are always greater than it`s value.

Example

Time complexity : O(n)

Algorithm

a. We use merge sort for merging linked lists.

b. We recursively flatten the lists by merge the current list with already flatten list.

c. We use down pointer to link nodes of the flattened list.

d. In merge function we compare data values of head nodes and put smaller one in flatten list.

Algorithm working

C++ Program

#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
    int data;
    struct LLNode* right;
    struct LLNode* down;  
};

/* Function to insertAtBeginning ListA node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->right = NULL;
    curr->down = *head;
    *head = curr; 
    //O(1) constant time
}
 
//display linked list
void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    while(temp!=NULL)
        {
            if(temp->down!=NULL)
            cout<<temp->data<<"->";
            else
            cout<<temp->data;
            
            temp=temp->down; //move to right node
        }
        //O(number of nodes)
    cout<<endl;
}
 
//Merge sort of ListA and ListB
struct LLNode* MergeSort(struct LLNode* ListA, struct LLNode* ListB )
{
    //Base cases
    if (ListA == NULL)
    {
        return ListB;
    }
    if (ListB == NULL)
    {
        return ListA;
    }
    //compare data of heads and add smaller to root
    struct LLNode* result;
    if (ListA->data < ListB->data)
    {
        result = ListA;
        result->down = MergeSort(ListA->down, ListB);
    }
    else
    {
        result = ListB;
        result->down = MergeSort(ListA, ListB->down);
    }
 
    return result;
}
 
//Function that flattens the given list
struct LLNode* flatten(struct LLNode* root)
{
    if (root == NULL || root->right == NULL)
    {
        return root;
    }
    //Merge right with already flattens
    return MergeSort(root,flatten(root->right) );
}
 
//Main function
int main()
{
    //Given linked list
    struct LLNode* root = NULL;
 
    insertAtBeginning(&root, 14);
    insertAtBeginning(&root, 8);
    insertAtBeginning(&root, 7);
 
    insertAtBeginning(&(root->right), 6);
    insertAtBeginning(&(root->right), 4);
    
    insertAtBeginning(&(root->right->right), 18);
    insertAtBeginning(&(root->right->right), 13);
    insertAtBeginning(&(root->right->right), 9);

    insertAtBeginning(&(root->right->right->right), 18);
    insertAtBeginning(&(root->right->right->right), 17);
    insertAtBeginning(&(root->right->right->right), 15);
    insertAtBeginning(&(root->right->right->right), 11); 
 
    insertAtBeginning(&(root->right->right->right->right), 16);
   

    root = flatten(root);
    
    cout<<"Output (sorted)flatten List is: ";
    display(&root);
 
    return 0;
}

READ  Insert Node in the Sorted Linked List

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions