Untitled

package optimized;

public class Listpartition {
	
	static ListNode lesshead=null;
	static ListNode lesstail=null;
	
	static ListNode equalhead=null;
	static ListNode equaltail=null;
	
	static ListNode greaterhead=null;
	static ListNode greatertail=null;
	
	
	static void printList(ListNode head)
	{
		ListNode temp = head;
	    while (temp != null)
	    {
	        System.out.print(temp.val + " --> ");
	        temp = temp.next;
	    }
	}
	
	public static void main(String[] args)
	{
	    /* Start with the empty list */
	    ListNode head = new ListNode(3);
	    head.next = new ListNode(2);
	    head.next.next = new ListNode(1);
	    head.next.next.next = new ListNode(5);
	    head.next.next.next.next = new ListNode(10);
	    head.next.next.next.next.next = new ListNode(2);
	    head.next.next.next.next.next.next = new ListNode(1);
	 
	    System.out.println("Before: ");
	    printList(head);
	    
	    int x = 5;
	    
	    head = partition(head, x);
	    
	    System.out.println("After: ");
	    printList(head);
	}
	
	public static void insertAtEnd(ListNode head, ListNode tail, int value) {
		ListNode newNode = new ListNode(value);
		
		if(head == null) {
			head = tail = newNode;
		}
		else {
			tail.next = newNode;
			tail = newNode;
		}
//		return head;
	}
	
	public static ListNode partition( ListNode head , int x) {
		
		
		ListNode curr = head;
		
		while(curr != null) {
			
//			System.out.println("curr value: " + curr.val);
			
			if(curr.val < x)
				insertAtEnd(lesshead, lesstail, curr.val);
			
			if(curr.val == x)
				insertAtEnd(equalhead, equaltail, curr.val);
			
			if(curr.val > x)
				insertAtEnd(greaterhead, greatertail, curr.val);
			
			curr = curr.next;
		}
		
		System.out.println("lesshead: ");
		printList(lesshead);
		
		System.out.println("equalhead: ");
		printList(equalhead);
		
		System.out.println("greaterhead: ");
		printList(greaterhead);
		
		System.out.println("After merger 1 & 2");
		printList(lesshead);
		
		System.out.println("After merger 1 & 2 & 3");
		printList(lesshead);
		
		lesstail.next = equalhead;
		equaltail.next = greaterhead;
	    
	    return lesshead;
	  }

}