26. Flatten linked list

26. Flatten linked list

Problem link :- click here

package Linked_List;

class Node3
{
	int data;
	Node3 next;
	Node3 bottom;
	
	Node3()
	{
		this.next = null;
		this.bottom = null;
	}
	Node3(int a)
	{
		this.data = a;
		this.next = null;
		this.bottom = null;
	}
}

class TwoSideLinkedList
{
	Node3 head;
	
	public void push(Node3 head_ref, int a)
	{
		Node3 node = new Node3(a);
		
		if(this.head == null)
			this.head = node;
		else if(head_ref == head)
		{
			Node3 temp = head;
			while(temp.bottom != null)
				temp = temp.bottom;
			temp.bottom = node;
		}
		else
		{
			//checking if already there is a head in that column
			Node3 temp = head;
			while(temp.next != head_ref  &&  temp.next != null)
				temp = temp.next;
			
			if(temp.next == null)
				temp.next = node;
			else 
			{
				temp = temp.next;
				while(temp.bottom != null)
					temp = temp.bottom;
				temp.bottom = node;
			}
		}
	}
	
	public void print(Node3 head_ref)
	{
		Node3 temp = head_ref;
		for(temp=head_ref; temp!=null; temp=temp.bottom)
			System.out.print(temp.data + "  ");
		System.out.println();
	}
}

public class LinkedList__26
{
	/*
	 	Given a linked list of size n, where every node represents a sub-linked-list and 
	 	contains two pointers:
	 		1 -> a 'next' pointer to the next node
	 		2 -> a 'bottom' pointer to a linked list where this node is head.
	 	Each sub-linked-list is in sorted order.
	 	Flatten the linked list such that all the nodes appear in a single level while 
	 	maintaining the sorted order.
        	 			5  ->  10  ->  19  ->  28
        	 			|       |       |       |
        	 			7      20      22      35
        	 			|       |       |
        	 			8      50      40
        	 			|               |
        	 			30             45

	 		output :  	5  7  8  10  19  20  22  28  30  35  40  45  50
	 	
	 	Lets merge method of the mergeSort 
	 */
	
	static Node3 merge(Node3 head1, Node3 head2)
	{
		if(head1 == null)
			return head2;
		if(head2 == null)
			return head1;
		
		Node3 result;
		if(head1.data <= head2.data)
		{
			result = head1;
			result.bottom = merge(head1.bottom, head2);
		}
		else
		{
			result = head2;
			result.bottom = merge(head1, head2.bottom);
		}
		
		return result;
	}
	
	static Node3 flattenTwoSideLinkedList(Node3 head)
	{
		if(head == null  ||  head.next == null)
			return head;
		
		head.next = flattenTwoSideLinkedList(head.next);
		
		head = merge(head, head.next);
		
		return head;
	}
	
	public static void main(String[] args)
	{
		TwoSideLinkedList list = new TwoSideLinkedList();
		try {
		list.push(list.head, 5);
		list.push(list.head, 7);
		list.push(list.head, 8);
		list.push(list.head, 30);
		list.push(list.head.next, 10);
		list.push(list.head.next, 20);
		list.push(list.head.next.next, 19);
		list.push(list.head.next.next, 22);
		list.push(list.head.next.next, 50);
		list.push(list.head.next.next.next, 28);
		list.push(list.head.next.next.next, 35);
		list.push(list.head.next.next.next, 40);
		list.push(list.head.next.next.next, 45);
		
		list.print(list.head);
		list.print(list.head.next);
		list.print(list.head.next.next);
		list.print(list.head.next.next.next);
		}catch(NullPointerException e)
		{}
		
		list.head = flattenTwoSideLinkedList(list.head);
		System.out.println("\nAfter soting : ");
		list.print(list.head);
	}

}

Time complexity :- O(n1 * n2)
Space complexity :- O(1)