ronith
7/23/2018 - 8:20 AM

Flattening a Linked List

Given a linked list where every node represents a linked list and contains two pointers of its type: (i) Pointer to next node in the main list (we call it ‘right’ pointer in below code) (ii) Pointer to a linked list where this node is head (we call it ‘down’ pointer in below code). All linked lists are sorted. See the following example

   5 -> 10 -> 19 -> 28
   |    |     |     |
   V    V     V     V
   7    20    22    35
   |          |     |
   V          V     V
   8          50    40
   |                |
   V                V
   30               45

Write a function flatten() to flatten the lists into a single linked list. The flattened linked list should also be sorted. For example, for the above input list, output list should be 5->7->8->10->19->20->22->28->30->35->40->45->50.

Algo: 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.

Flattening a Linked List.cpp
content_copyfile_download
// https://www.geeksforgeeks.org/flattening-a-linked-list/
#include <iostream>
#include <list>
using namespace std;

struct linked_list {
    int data;
    struct linked_list *right;
    struct linked_list *down;
};
typedef struct linked_list node;

void print (node *n) {
    while(n) {
        cout<< n->data<< "->";
        n = n->down;
    }
    cout<< "NULL";
}

void insert (node** headref, int n) {
    node *temp = (node*)malloc(sizeof(node));
    temp->data = n;
    temp->down = NULL;

    if (*headref == NULL) {
        *headref = temp;
        return;
    }
    node *last = *headref;
    while (last->down)
        last= last->down;
    last->down= temp;
    return;
}

node* merge (node *a, node* b) {
    node *head = NULL;
    while (a && b) {
        if (a->data <= b->data) {
            insert(&head, a->data);
            a = a->down;
        }
        else {
            insert(&head, b->data);
            b = b->down;
        }
    }
    while (a) {
        insert(&head, a->data);
        a = a->down;
    }
    while (b) {
        insert(&head, b->data);
        b = b->down;
    }
    return head;
}

node *flatten (node *head) {
    cout<< "\njhvjhvjh\n";
    if (head ==NULL || head->right ==NULL)
        return head;
    return merge(head, flatten(head->right));
}

int main () {
    node *head=NULL;
    insert( &head, 5 );
    insert( &head, 7 );
    insert( &head, 8 );
    insert( &head, 30 );

    insert( &( head->right ), 10 );
    insert( &( head->right ), 20 );

    insert( &( head->right->right ), 19 );
    insert( &( head->right->right ), 22 );
    insert( &( head->right->right ), 50 );

    insert( &( head->right->right->right ), 02 );
    insert( &( head->right->right->right ), 35 );
    insert( &( head->right->right->right ), 40 );
    insert( &( head->right->right->right ), 45 );
    head=flatten(head);
    print(head);
}