> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/linked-list/86.-partition-list.md).

# 86. Partition List

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

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

<pre><code><strong>Input: head = [1,4,3,2,5,2], x = 3
</strong><strong>Output: [1,2,2,4,3,5]
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: head = [2,1], x = 2
</strong><strong>Output: [1,2]
</strong></code></pre>

&#x20;

**Constraints:**

* The number of nodes in the list is in the range `[0, 200]`.
* `-100 <= Node.val <= 100`
* `-200 <= x <= 200`

## Intuition

```
Approach:

Maintain large_start, large_end, Similarly for small start and end

These are going to track the larger than x chain start and end points
And similarly for start pointers

At every step
Modify the end pointers after breaking the existing links accoringly

Then at end, join the start end to large start
If start end is null return large start

```

### Links

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

### Video Links

### Approach 1:

```
Pointer change
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode *trav=head;
        ListNode *temp, *ss=nullptr, *se=nullptr, *ls=nullptr, *le=nullptr;

        while(trav != nullptr){
            if(trav->val < x){
                if(ss == nullptr)
                    ss = se = trav;

                else{
                    se->next = trav;
                    se = trav;
                }

                temp = se->next;
                se->next = nullptr;
                trav = temp;
            }

            else{
                if(ls == nullptr)
                    ls = le = trav;

                else{
                    le->next = trav;
                    le = trav;
                }
                
                temp = le->next;
                le->next = nullptr;
                trav = temp;
            }
        }

        if(ss == nullptr)
            return ls;

        se->next = ls;
        return ss;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###