Printed a sorted multi-level linked list

Given a linked list, where each node has a pointer to the head of its child list (in addition to the next pointer). The child list is a normal linked list with each node having one data and one pointer to the next node in the child list.

Let the lists be arranged (as above) in a way that:

• Values in the main list are all sorted.
• Values in each child list is sorted.
• All values in a child list are less than the value of next node in the main list.

The structure of Node in the main list is different from the structure of the node in the child list as shown below:

Given a pointer to the head of such a list, write code to print all the values (in main list and all child lists) in sorted order. The output for given list should be:

1 2 4 5 7 9 12 15 20 29 40 50 52 70

Solution:

The solution to this problem is an extension of the simple problem of printing a linked list. If we want to print only the top list (1, 5, 20, 40). Then, we simply need to move to the next node using the next pointer in the main Node structure.
The code to traverse the main list (without visiting any of the child node) is same as traversing a singly linked list

void printTopList(Node* h)
{
  while(h != NULL)
  {
    cout<< h->data<<" ";
    h = h->next;
  }
  cout<<"\n";
}

If we want to print child list of any node, then this is also the exact same code. The only difference is in the signature of the function (because now the function will receive a pointer to ChildNode and not Node*)

void printDownList(ChildNode* h)
{
  while(h != NULL)
  {
    cout<< h->data<<" ";
    h = h->next;
  }
  cout<<"\n";
}

The logic to print all the values in the entire list (both top and child lists) is a combination of above two as shown below:

void printAllValuesSorted(Node *h)
{
  if(h==NULL) return ;
  while(h != NULL)
  {
    cout << h->data << " ";
    ChildNode *temp = h->down;
    while(temp != NULL)
    {
      cout << temp->data << " ";
      temp = temp->next;
    }
    h = h->next;
  }
  cout<<endl;
}

The time taken by the above function is O(n), where n is the number of total number of nodes in the entire structure. Below is the complete program in C++. It also has a function to create the list.

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <queue>
using namespace std;
struct ChildNode
{
  int data;
  ChildNode* next;
  // CONSTRUCTOR
  ChildNode(int x): data(x), next(NULL){}
};
struct Node
{
  int data;
  ChildNode* down;
  Node* next;
//  // CONSTRUCTOR
  Node(int x): data(x), down(NULL), next(NULL){}
};
Node *createLists()
{
  Node* h = new Node(1);
  h->next = new Node(5);
  h->next->next = new Node(20);
  h->next->next->next = new Node(40);
  h->down = new ChildNode(2);
  h->down->next = new ChildNode(4);
  h->next->down = new ChildNode(7);
  h->next->down->next = new ChildNode(9);
  h->next->down->next->next = new ChildNode(12);
  h->next->down->next->next->next = new ChildNode(15);
  h->next->next->down = new ChildNode(29);
  h->next->next->next->down = new ChildNode(50);
  h->next->next->next->down->next = new ChildNode(52);
  h->next->next->next->down->next->next = new ChildNode(70);
  return h;
}
void printTopList(Node* h)
{
  while(h != NULL)
  {
    cout<< h->data<<" ";
    h = h->next;
  }
  cout<<"\n";
}
void printDownList(ChildNode* h)
{
  while(h != NULL)
  {
    cout<< h->data<<" ";
    h = h->next;
  }
  cout<<"\n";
}
void printAllValuesSorted(Node *h)
{
  if(h==NULL) return ;
  while(h != NULL)
  {
    cout << h->data << " ";
    ChildNode *temp = h->down;
    while(temp != NULL)
    {
      cout << temp->data << " ";
      temp = temp->next;
    }
    h = h->next;
  }
  cout<<endl;
}
int main()
{
  Node *h = createLists();
  // PRINTING THE TOP LIST
  cout<<"TOP LIST : ";
  printTopList(h);
  // PRINTING ALL THE VALUES IN SORTED ORDER
  cout<<"SORTED NODES : ";
  printAllValuesSorted(h);
  cout<<endl;
  return 0;
}