public ListNode partition(ListNode head, int x) {
    	ListNode firstPart = null;
    	ListNode firsttail = null;
    	ListNode lastPart = null;
    	ListNode lasttail = null;
    	
    	ListNode node = head;
    	while (node != null)
    	{
    		if (node.val < x)
    		{
    			if (firstPart == null)
    			{
    				firstPart = node;
    				firsttail = node;
    			}
    			else
    			{
    				firsttail.next = node;
    				firsttail = firsttail.next;
    			}
    		}
    		else
    		{
    			if (lastPart == null)
    			{
    				lastPart = node;
    				lasttail = node;
    			}
    			else
    			{
    				lasttail.next = node;
    				lasttail = lasttail.next;
    			}
    		}
    		node = node.next;
    	}
    	firsttail.next = lastPart;
    	lasttail.next = null;
    	
    	return firstPart;
    }