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
*/
//create the main linked list
LinkedList mainList= new LinkedList();
/**Node 1 of main List*/
//create first node of main linked list
ListNode node = new ListNode(5);
//add the node to the main list
mainList.add(node);
//create the sub-list of the main nodes
LinkedList subList = new LinkedList();
//create the first node of the sub-list
ListNode subListOfNode= new ListNode(7);
//add the sub-list node to the sub-list
subList.add(subListOfNode);
//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);
//add it to the sub-list
subList.add(subListOfNode);
//create the third node of the sub-list
subListOfNode = new ListNode(30);
//add it to the sub-list
subList.add(subListOfNode);
/**Node 2 of main List*/
//create a new node of the main-list
node = new ListNode(10);
//add it to the main list
mainList.add(node);
//create a new sub-list for the second node of the main list
subList = new LinkedList();
//create the first node of the sub-list
subListOfNode= new ListNode(20);
//add the sub-list node to the sub-list
subList.add(subListOfNode);
//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
mainList.add(node);
//create a new sub-list for the second node of the main list
subList = new LinkedList();
//create the first node of the sub-list
subListOfNode= new ListNode(22);
//add the sub-list node to the sub-list
subList.add(subListOfNode);
//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
subList.add(subListOfNode);
/**Node 4 of main List*/
//create a new node of the main-list
node = new ListNode(28);
//add it to the main list
mainList.add(node);
//create a new sub-list for the second node of the main list
subList = new LinkedList();
//create the first node of the sub-list
subListOfNode= new ListNode(35);
//add the sub-list node to the sub-list
subList.add(subListOfNode);
//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
subList.add(subListOfNode);
//create the second node of the sub-list
subListOfNode= new ListNode(45);
//add the sub-list node to the sub-list
subList.add(subListOfNode);
//loop through main list and insert each node of the sub-list at the appropriate locate
ListNode temp= mainList.head;
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
ListNode mainTemp= mainList.head;
//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();
}
}
}
}
LinkedList Class:
package additional_problems.linkedList;
/**
* Created by aarushi on 24/6/21.
*/
public class LinkedList {
//data fields
//head node
ListNode head;
//constructor to initialize head node
public LinkedList() {
head = null;
}
//function to add node to the end of the linked list
public void add(ListNode node) {
//if list is empty then set head equal to the node
if (head == null) {
head = node;
node.setNext(null);
} else {
//create a pointer- temp
ListNode temp = head;
//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
if (head == null) {
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) {
System.out.println(head.getData() + " deleted");
head = head.getNext();
} else {
//pointer temp which will traverse the linked list
ListNode temp = head;
//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 {
throw new Exception("Node not found");
}
}
}
public ListNode find(LinkedList node) {
return null;
}
//Method to print the linked list
public void print() throws Exception {
//if the list is empty, throw an exception
if (head == null) {
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() {
if (head == null) {
return;
} else {
ListNode temp = head;
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
int linkedListLength = 0;
//start from the head of the linked list
ListNode temp = head;
//traverse the linked list till the last node i.e when temp reaches null
while (temp != null) {
linkedListLength++;
temp = temp.getNext();
}
return linkedListLength;
}
//method to get the middle of the linked list
public int getMiddle() throws Exception {
//throw an exception if list is null
if (head == 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
ListNode temp = head;
//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
if(head==null){
return;
}
//if the ith index is zero then set it to head
else if (i==0){
node.setNext(head);
head=node;
}
else {
//temp: pointer which traverses the linked list
ListNode temp= head;
//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;
}
}