In my solution, I have created two list of smaller and larger values than x. In the end if the value is present in the list join the list considering the value in the middle of left and right or else I join in simply.

But my solution fails at [1,3,2], 2 Your answer : [1,2,3] Expected answer : [1,3,2]

Shouldn't the answer be [1,2,3]. Please correct me If am wrong

public class Solution {

public ListNode partition(ListNode head, int x) {

```
if(head == null || head.next==null){
return head;
}
boolean valuePresent = false;
ListNode left = null;
ListNode right = null;
ListNode temp = head;
ListNode rightHead = null;
while(temp != null){
if(temp.val < x){
if(left == null){
left = new ListNode(temp.val);
head = left;
}
else{
ListNode newN = new ListNode(temp.val);
left.next = newN;
left = left.next;
}
}
else if (temp.val > x){
if(right == null){
right = new ListNode(temp.val);
rightHead = right;
}
else{
ListNode newN = new ListNode(temp.val);
right.next = newN;
right = right.next;
}
}
else{
valuePresent = true;
}
temp = temp.next;
}
if(valuePresent){
ListNode valN = new ListNode(x);
if(left!=null){
left.next = valN;
}
valN.next = rightHead;
}
else{
if(left!=null){
left.next = rightHead;
}
}
return head;
}
}
```