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;
}

Translate »