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.

**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]

**Constraints:**

The number of nodes in the list is in the range [0, 200].

-100 <= Node.val <= 100

-200 <= x <= 200

**Solution:**

```
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode head1 = new ListNode(-1);
ListNode head2 = new ListNode(-1);
ListNode small = head1;
ListNode large = head2;
ListNode current = head;
while(current!=null)
{
if(current.val<x)
{
small.next=current;
small=current;
}
else
{
large.next = current;
large=current;
}
current = current.next;
}
large.next=null;
small.next = head2.next;
return head1.next;
}
}
```

## Comments