# 86. Partition List

&#x20;**86. Partition List**

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`.\\

**My Solutions:**

* 分成两个head，小的加入small，大的加入big，最后合并
* Time: O(n);
* Space: O(n) 【每次复制node】

```
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummySmall = new ListNode(0);
        ListNode dummyLarge = new ListNode(0);
        ListNode dS = dummySmall; //记录head
        ListNode dL = dummyLarge; //记录head
        
        while (head != null) {
            if (head.val < x) {
                dummySmall.next = head;
                dummySmall = dummySmall.next;
            } else {
                dummyLarge.next = head;
                dummyLarge = dummyLarge.next;
            }
            head = head.next;
        }
        dummySmall.next = dL.next;
        dummyLarge.next = null;    
        return dS.next;    
    }
}
```
