Question: You are given a linked list where every node represents a linked list. All linked lists are sorted. You have to flatten the lists into a single linked list. The flattened linked list should also be sorted. For example, for the below input list, output list should be 5->7->8->10->19->20->22->28->30->35->40->45->50.

``````
/**
5 -> 10 -> 19 -> 28
|    |     |     |
V    V     V     V
7    20    22    35
|          |     |
V          V     V
8          50    40
|                |
V                V
30               45
``````
```package additional_problems.linkedList;

/**
* Created by aarushi on 27/6/21.
*/
public class P02SortSubList {

public static void main(String [] args){

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

/**Node 1 of main List*/
//create first node of main linked list
ListNode node = new ListNode(5);
//add the node to the main list
//create the sub-list of the main nodes
//create the first node of the sub-list
ListNode subListOfNode= new ListNode(7);
//add the sub-list node to the sub-list
//link the sub-list pointer of main list node to the first node of the sub-list
node.setSubList(subListOfNode);
//create the second node of the sub-list
subListOfNode = new ListNode(8);
//create the third node of the sub-list
subListOfNode = new ListNode(30);

/**Node 2 of main List*/
//create a new node of the main-list
node =  new ListNode(10);
//add it to the main list
//create a new sub-list for the second node of the main list
//create the first node of the sub-list
subListOfNode= new ListNode(20);
//add the sub-list node to the sub-list
//link the sub-list pointer of main list node to the first node of the sub-list
node.setSubList(subListOfNode);

/**Node 3 of main List*/
//create a new node of the main-list
node =  new ListNode(19);
//add it to the main list
//create a new sub-list for the second node of the main list
//create the first node of the sub-list
subListOfNode= new ListNode(22);
//add the sub-list node to the sub-list
//link the sub-list pointer of main list node to the first node of the sub-list
node.setSubList(subListOfNode);
//create the second node of the sub-list
subListOfNode= new ListNode(50);
//add the sub-list node to the sub-list

/**Node 4 of main List*/
//create a new node of the main-list
node =  new ListNode(28);
//add it to the main list
//create a new sub-list for the second node of the main list
//create the first node of the sub-list
subListOfNode= new ListNode(35);
//add the sub-list node to the sub-list
//link the sub-list pointer of main list node to the first node of the sub-list
node.setSubList(subListOfNode);
//create the second node of the sub-list
subListOfNode= new ListNode(40);
//add the sub-list node to the sub-list
//create the second node of the sub-list
subListOfNode= new ListNode(45);
//add the sub-list node to the sub-list

//loop through main list and insert each node of the sub-list at the appropriate locate
while(temp!=null){
sort(mainList, temp);
temp=temp.getNext();
}
mainList.printNoException();
}

public static void sort(LinkedList mainList, ListNode node){
//if sub-list is null then return
if(node.getSubList()==null){
return;
} else {
//temp: pointer to traverse the sub-list
ListNode temp= node.getSubList();

//traverse the sub-list till the last element
while(temp!=null){
//print the main list after every insertion
mainList.printNoException();

//mainTemp: pointer to traverse through the mainList to find appropriate location to insert the sub-list node
//index: indicates the index at which the sub-list node should be inserted into the main list
int index=0;
//found: indicates whether the node has been inserted in the main list
boolean found = false;

//traverse the main list
while(mainTemp!=null){
//check if the value of the sub-list node is less than the main list node
if(temp.getData()<mainTemp.getData()){
//create a new node which will have the same value of sub-list-node
ListNode insertNode = new ListNode(temp.getData());
//insert the node
mainList.insert(insertNode, index);
//indicate that the node has been inserted
found = true;
//break out of the loop
break;
} else {
//increase the index by one if the node hasn't been inserted
index++;
//move onto the next node on the main list
mainTemp=mainTemp.getNext();
}
}
//if the node hasn't been inserted yet then insert the node at the end of main-list
if (!found) {
ListNode insertNode = new ListNode(temp.getData());
mainList.insert(insertNode,index);
}
//move to the next node in the sub-list
temp=temp.getNext();
}
}
}

}
```

```package additional_problems.linkedList;

/**
* Created by aarushi on 24/6/21.
*/
//data fields

}

//if list is empty then set head equal to the node
node.setNext(null);
} else {
//create a pointer- temp
//iterate to the last element
while (temp.getNext() != null) {
temp = temp.getNext();
}
//insert the node at the end of the list
temp.setNext(node);
node.setNext(null);
}
}

//method to delete the last node of the linked list
public void delete(ListNode node) throws Exception {

//throw exception if the list is empty
throw new Exception("List is empty");
}

//if the node passed is the head node then change the head pointer to the next node
else if (node == head) {
} else {
//pointer temp which will traverse the linked list

//find the node which points to the node to be deleted
while (temp.getNext() != node && temp != null) {
}

//if node if found then delete the node otherwise throw an exception
if (temp != null) {
System.out.println(temp.getNext().getData() + " deleted");
temp.setNext(node.getNext());
} else {
}

}
}

return null;
}

//Method to print the linked list
public void print() throws Exception {
//if the list is empty, throw an exception
throw new Exception("List is Empty");
} else {
ListNode temp = head; //create a pointer- temp that will traverse through the linked list
while (temp != null) { //traverse to the last element of the linked list
System.out.print(temp.getData() + " "); //print the data of every node
temp = temp.getNext();  //set pointer to the next node
}
System.out.println();
}
}

public void printNoException() {
return;
} else {
while (temp != null) {
System.out.print(temp.getData() + " ");
temp = temp.getNext();
}
System.out.println();
}
}

//method to find the length of the linked list
public int findLength() {
//set the length to zero initially

//traverse the linked list till the last node i.e when temp reaches null
while (temp != null) {
temp = temp.getNext();
}
}

//method to get the middle of the linked list
public int getMiddle() throws Exception {

//throw an exception if list is null
throw new Exception("List is Empty");
} else {
//find the length of the linked list
int length = findLength();

//index: to keep a count of the number of nodes traversed
//middle: indicates the middle node number
int index = 0, middle = length / 2;

//temp: pointer which traverses the linked list

//traverse till the middle node
while (index != middle) {
temp = temp.getNext();
index++;
}
//return the value of the middle node
return temp.getData();
}
}

//method to insert node at the ith index
public void insert(ListNode node, int i){
//If the list is empty return
return;
}

//if the ith index is zero then set it to head
else if (i==0){
}

else {
//temp: pointer which traverses the linked list
//index: keep count of number of nodes traversed
int index=0;
//traverse the list till the (i-1) index
while(index!=(i-1)){
temp=temp.getNext();
index++;
}
//insert the node at the ith index
node.setNext(temp.getNext());
temp.setNext(node);
}
}

}
```

ListNode Class:

```package additional_problems.linkedList;

/**
* This class is the type declaration for a linked list
* Created by aarushi on 24/6/21.
*/
public class ListNode {
//data fields
private int data; //stores the value of the node
private ListNode next; //stores the reference of the next node
private ListNode subList;

//constructor to initialize the value of the node
public ListNode(int data){
this.data= data;
this.subList=null;
}

//accessor method to get the value stored in data
public int getData() {
return this.data;
}

//mutator method to change the value of data
public void setData(int data) {
this.data = data;
}

//accessor method which returns the reference of the next node
public ListNode getNext() {
return this.next;
}

//mutator method which changes the reference of the next node
public void setNext(ListNode next) {
this.next = next;
}

public ListNode getSubList() {
return subList;
}

public void setSubList(ListNode subList) {
this.subList = subList;
}
}
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.