Linked List: Flatten a linked list

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

Leave a Reply

PHP JS HTML CSS BASH PYTHON CODE

Your email address will not be published.

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

%d bloggers like this: