Absolute_list_sorting.java

/*Please note that it's Function problem i.e.
you need to write your solution in the form of Function(s) only.
Driver Code to call/invoke your function is mentioned above.*/

/* The structure of the node of the Linked List is
class Node
{
   int data;
   Node next;
   Node(int d) {data = d; next = null; }
 }
*/
class GfG
{
	Node sortedList(Node head)
	{
	    Node curr = head;
	    Node add = null;
	    Node add_start  = null;
	    Node sub = null;
	    Node sub_start = null;
	    Stack<Integer> stack = new Stack<Integer>();
	    while(curr != null){
	        if(curr.data >= 0){
	            if(add == null){
	                add = new Node(curr.data);
	                add_start = add;
	            }
	            else{
	                add.next = new Node(curr.data);
	                add = add.next;
	            }
	        }
	        else{
	            stack.push(curr.data);
	            
	        }
	        curr = curr.next;
	    }
	    if(add != null)
	        add.next =null;
	    if(!stack.isEmpty()){
	        while(!stack.isEmpty()){
	            int val =stack.pop();
	            if(sub == null){
	                sub = new Node(val);
	                sub_start = sub;
	            }
	            else{
	                sub.next = new Node(val);
	                sub = sub.next;
	                
	            }
	        }
	        sub.next = add_start;
	        return sub_start;
	    }
	    else{
	        return add_start;
	    }
	    
	}
}