# 0086. Partition List

<https://leetcode.com/problems/partition-list>

## Description

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

![](https://assets.leetcode.com/uploads/2021/01/04/partition.jpg)

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

## ac1

modify in place

```java
class Solution {
    public ListNode partition(ListNode head, int x) {
        // edge cases
        if (head == null || head.next == null) return head;

        //dummy, smallTail, prev, curr
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        ListNode smallTail = dummy, prev = dummy, curr = head;
        // walk
        while (curr != null) {
            if (curr.val < x && prev.val >= x) {
                // take out
                ListNode tmp = curr;
                prev.next = curr.next;
                curr = curr.next;
                // insert
                tmp.next = smallTail.next;
                smallTail.next = tmp;
                smallTail = smallTail.next;
            } else {
                prev = curr;
                curr = curr.next;
                if (smallTail.next.val < x) smallTail = smallTail.next;
            }
        }

        return dummy.next;
    }
}
// dummy, smallTail, prev, curr
// walk, when val < x, prev.next = curr.next, tmp = curr.
// insert tmp after smallTail
```

## ac2

use two dummy node. this one is more concise and less error prone.

```java
class Solution {
    public ListNode partition(ListNode head, int x) {
        // edge cases
        if (head == null || head.next == null) return head;

        //dummy, smallTail, prev, curr
        ListNode dummy1 = new ListNode(0);
        ListNode dummy2 = new ListNode(0);
        ListNode curr1 = dummy1, curr2 = dummy2;
        // walk
        while (head != null) {
            if (head.val < x) {
                curr1.next = head;
                curr1 = curr1.next;
            } else {
                curr2.next = head;
                curr2 = curr2.next;
            }
            head = head.next;
        }

        curr2.next = null;
        curr1.next = dummy2.next;

        return dummy1.next;
    }
}
```