# [LeetCode 86] Partition List

### 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) {
ListNode PH = new ListNode(1);
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;
}
``````