Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

&nbsp;
Example 1:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]


Example 2:

Input: head = [2,1], x = 2
Output: [1,2]


&nbsp;
Constraints:


	The number of nodes in the list is in the range [0, 200].
	-100 &lt;= Node.val &lt;= 100
	-200 &lt;= x &lt;= 200


# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        lessthan = []
        greateql = []

        while head:
            if head.val < x:
                lessthan.append(head.val)
            else:
                greateql.append(head.val)
            head = head.next

        h = res = ListNode()

        for i in range(len(lessthan)):
            res.next = ListNode(lessthan[i])
            res = res.next
        for i in range(len(greateql)):
            res.next = ListNode(greateql[i])
            res = res.next

        return h.next
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode left = new ListNode(0);
        ListNode right = new ListNode(0);
        
        ListNode leftTail = left;
        ListNode rightTail = right;
        
        while(head != null){
            if(head.val < x){
                leftTail.next = head;
                leftTail = leftTail.next;
            }
            else{
                rightTail.next = head;
                rightTail = rightTail.next;
            }
            head = head.next;
        }
        
        leftTail.next = right.next;
        rightTail.next = null;
        
        return left.next;
    }
}
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode *left = new ListNode(0);
        ListNode *right = new ListNode(0);
        
        ListNode *leftTail = left;
        ListNode *rightTail = right;
        
        while(head != NULL){
            if(head->val < x){
                leftTail->next = head;
                leftTail = leftTail->next;
            }
            else{
                rightTail->next = head;
                rightTail = rightTail->next;
            }
            head = head->next;
        }
        
        leftTail->next = right->next;
        rightTail->next = NULL;
        
        return left->next;
    }
};
var partition = function(head, x) {
    if (!head) {
        return head;
    }
    const less = [];
    const greater = [];
    let concat;
    rec(head);
    return head;
    
    
    function rec(currentNode) {
        if (currentNode.val < x) {
            less.push(currentNode.val);
        } else {
            greater.push(currentNode.val);
        }
        if (!currentNode.next) {
            concat = [...less, ...greater];
            currentNode.val = concat.pop();       
            return;
        }
        rec(currentNode.next);
        currentNode.val = concat.pop();
    }
    
};
Partition List