### Question

Given 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.

For example,

Given `1->4->3->2->5->2`

and *x* = 3,

return `1->2->2->4->3->5`

.

### Stats

Frequency | 3 |

Difficulty | 3 |

Adjusted Difficulty | 4 |

Time to use | ---------- |

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

**This question is not very difficult**, but can be confusing if the code don’t have good logic.

### Solution

There is no fancy algorithm solution. I got it wrong in 10 submissions at first. After a few days, I did this problem again and passed with 1 attempt.

So just keep practicing.

### Code

**my code**

```
public ListNode partition(ListNode head, int x) {
if (head == null) return head;
ListNode PH = new ListNode(1);
PH.next = head;
ListNode left = PH, preRight = PH, right = head;
while (right != null) {
if (right.val < x) {
if (preRight != left) {
preRight.next = right.next;
right.next = left.next;
left.next = right;
left = right;
right = preRight.next;
} else {
left = left.next;
preRight = left;
right = right.next;
}
} else {
preRight = right;
right = preRight.next;
}
}
return PH.next;
}
```