# Partition List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/partition-list)
Canonical: https://scaleengineer.com/dsa/problems/partition-list
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Linked List
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Microsoft](https://scaleengineer.com/companies/microsoft), [tcs](https://scaleengineer.com/companies/tcs)
---
## Problem
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.glich.co/dsa/partition-list/image0.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`

# Approaches
## Using Auxiliary Lists
This approach involves converting the linked list into a more flexible data structure, like an array or list, to make partitioning easier. We iterate through the original list, segregating nodes into two separate lists based on the pivot value `x`. One list holds nodes with values less than `x`, and the other holds nodes with values greater than or equal to `x`. After populating these lists, we link them together to form the final partitioned linked list.
**Time:** O(N) · **Space:** O(N)
**Pros:** Conceptually straightforward and easy to implement.; Separates the concern of partitioning from the complexities of linked list pointer manipulation.
**Cons:** Requires O(N) extra space for the auxiliary lists, which is inefficient for large inputs.; This approach is not in-place; it reconstructs the list structure rather than just rearranging pointers.
### Explanation
The core idea is to offload the linked list nodes into two separate lists. This simplifies the partitioning logic as we don't have to manage `next` pointers during the segregation phase. 

First, we iterate through the linked list once. During this traversal, we check each node's value against `x`. If the value is smaller, we add the node to a `lesserNodes` list. If it's greater or equal, we add it to a `greaterOrEqualNodes` list. Because we add nodes to the end of these lists in the order we encounter them, the original relative ordering within each partition is naturally preserved.

Once the segregation is complete, we construct the new linked list. We create a dummy head to simplify the building process. We first link all nodes from the `lesserNodes` list, and then we link all nodes from the `greaterOrEqualNodes` list. It's crucial to set the `next` pointer of the very last node to `null` to correctly terminate the list.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        // Store nodes in two separate lists
        java.util.List<ListNode> lesserNodes = new java.util.ArrayList<>();
        java.util.List<ListNode> greaterOrEqualNodes = new java.util.ArrayList<>();

        ListNode current = head;
        while (current != null) {
            if (current.val < x) {
                lesserNodes.add(current);
            } else {
                greaterOrEqualNodes.add(current);
            }
            current = current.next;
        }

        // Reconstruct the linked list
        ListNode dummy = new ListNode(0);
        ListNode newTail = dummy;

        for (ListNode node : lesserNodes) {
            newTail.next = node;
            newTail = newTail.next;
        }

        for (ListNode node : greaterOrEqualNodes) {
            newTail.next = node;
            newTail = newTail.next;
        }

        // Terminate the list
        newTail.next = null;

        return dummy.next;
    }
}
```
### Algorithm
*   1. Create two auxiliary `ArrayLists`: one to store nodes with values less than `x` (`lesserNodes`) and another for nodes with values greater than or equal to `x` (`greaterOrEqualNodes`).
*   2. Traverse the input linked list from the `head`.
*   3. For each node encountered, check its value. If `node.val < x`, add the node to `lesserNodes`. Otherwise, add it to `greaterOrEqualNodes`.
*   4. After the entire list has been traversed, the two `ArrayLists` will contain all the nodes, partitioned and with their relative order preserved within each partition.
*   5. Create a new dummy `ListNode` to serve as the starting point for the result list.
*   6. Iterate through `lesserNodes` and append each node to the new list.
*   7. Then, iterate through `greaterOrEqualNodes` and append each node to the end of the new list.
*   8. Finally, set the `next` pointer of the last node in the newly formed list to `null` to prevent cycles.
*   9. Return the `next` of the dummy node, which is the head of the final partitioned list.

## Two-Pointer Approach
This is an optimal, in-place approach that uses constant extra space. The idea is to create two separate linked lists during a single pass through the original list. One list will contain all nodes with values less than `x`, and the other will contain all nodes with values greater than or equal to `x`. We use two dummy heads to simplify the process of building these lists. After iterating through the original list, we simply connect the tail of the 'lesser' list to the head of the 'greater' list.
**Time:** O(N) · **Space:** O(1)
**Pros:** Extremely efficient in terms of space, using only O(1) extra space.; Requires only a single pass through the linked list.; Preserves the original nodes, only rearranging their pointers, which is memory-efficient.
**Cons:** Requires careful pointer manipulation to correctly link the lists and avoid creating cycles.
### Explanation
This approach avoids the O(N) space complexity of the previous method by rearranging the existing nodes in-place.

We start by creating two sentinel or dummy nodes, `lesserHead` and `greaterHead`. These nodes provide a fixed entry point to our two new lists: the 'lesser' list and the 'greater' list. We also maintain two tail pointers, `lesserTail` and `greaterTail`, which will always point to the last node of their respective lists, allowing for O(1) appends.

We then iterate through the original linked list node by node. For each node, we decide which list it belongs to based on its value compared to `x`. If `node.val < x`, we append it to the 'lesser' list using `lesserTail`. Otherwise, we append it to the 'greater' list using `greaterTail`. The key is that we are not creating new nodes, but simply redirecting the `next` pointers of the existing nodes.

After the single pass is complete, we have two distinct lists. The final step is to merge them. We link the end of the 'lesser' list (`lesserTail`) to the beginning of the 'greater' list (`greaterHead.next`). We must also set `greaterTail.next = null` to ensure the final merged list is properly terminated and doesn't contain a cycle.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        // Dummy head for the list of nodes less than x
        ListNode lesserHead = new ListNode(0);
        ListNode lesserTail = lesserHead;

        // Dummy head for the list of nodes greater than or equal to x
        ListNode greaterHead = new ListNode(0);
        ListNode greaterTail = greaterHead;

        ListNode current = head;
        while (current != null) {
            if (current.val < x) {
                // Append to the lesser list
                lesserTail.next = current;
                lesserTail = lesserTail.next;
            } else {
                // Append to the greater or equal list
                greaterTail.next = current;
                greaterTail = greaterTail.next;
            }
            current = current.next;
        }

        // Connect the lesser list with the greater list
        lesserTail.next = greaterHead.next;

        // Terminate the greater list to avoid cycles
        greaterTail.next = null;

        return lesserHead.next;
    }
}
```
### Algorithm
*   1. Initialize two dummy nodes, `lesserHead` and `greaterHead`, which will act as the heads of two new lists.
*   2. Initialize two tail pointers, `lesserTail` pointing to `lesserHead` and `greaterTail` pointing to `greaterHead`.
*   3. Traverse the original linked list starting from its `head` with a `current` pointer.
*   4. In each iteration, check the value of the `current` node:
    *   If `current.val < x`, append it to the end of the 'lesser' list by setting `lesserTail.next = current` and then advancing `lesserTail` to `current`.
    *   If `current.val >= x`, append it to the end of the 'greater' list by setting `greaterTail.next = current` and then advancing `greaterTail` to `current`.
*   5. Move `current` to the next node in the original list.
*   6. After the loop finishes, the original list has been fully traversed and its nodes are now split between the two new lists.
*   7. Connect the 'lesser' list to the 'greater' list. The end of the 'lesser' list is `lesserTail`, so set `lesserTail.next` to the start of the 'greater' list, which is `greaterHead.next`.
*   8. Terminate the combined list by setting `greaterTail.next = null`. This is a critical step to prevent cycles, as the last node of the 'greater' list might still be pointing to a subsequent node from the original list structure.
*   9. Return `lesserHead.next`, which is the head of the final, correctly partitioned list.

# Solutions
### CSharp

```csharp
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode Partition ( ListNode head , int x ) { ListNode l = new ListNode (); ListNode r = new ListNode (); ListNode tl = l , tr = r ; for (; head != null ; head = head . next ) { if ( head . val < x ) { tl . next = head ; tl = tl . next ; } else { tr . next = head ; tr = tr . next ; } } tr . next = null ; tl . next = r . next ; return l . next ; } }
```

### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode partition ( ListNode head , int x ) { ListNode d1 = new ListNode (); ListNode d2 = new ListNode (); ListNode t1 = d1 , t2 = d2 ; while ( head != null ) { if ( head . val < x ) { t1 . next = head ; t1 = t1 . next ; } else { t2 . next = head ; t2 = t2 . next ; } head = head . next ; } t1 . next = d2 . next ; t2 . next = null ; return d1 . next ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} x * @return {ListNode} */ var partition =
  function (head, x) {
    const d1 = new ListNode();
    const d2 = new ListNode();
    let t1 = d1,
      t2 = d2;
    while (head) {
      if (head.val < x) {
        t1.next = head;
        t1 = t1.next;
      } else {
        t2.next = head;
        t2 = t2.next;
      }
      head = head.next;
    }
    t1.next = d2.next;
    t2.next = null;
    return d1.next;
  };

```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * partition ( ListNode * head , int x ) { ListNode * d1 = new ListNode (); ListNode * d2 = new ListNode (); ListNode * t1 = d1 ; ListNode * t2 = d2 ; while ( head ) { if ( head -> val < x ) { t1 -> next = head ; t1 = t1 -> next ; } else { t2 -> next = head ; t2 = t2 -> next ; } head = head -> next ; } t1 -> next = d2 -> next ; t2 -> next = nullptr ; return d1 -> next ; } };
```

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def partition ( self , head : Optional [ ListNode ], x : int ) -> Optional [ ListNode ]: d1 , d2 = ListNode (), ListNode () t1 , t2 = d1 , d2 while head : if head . val < x : t1 . next = head t1 = t1 . next else : t2 . next = head t2 = t2 . next head = head . next t1 . next = d2 . next t2 . next = None return d1 . next
```