Solution: Partition List
Tags: algorithms, javascript, java, python
Published: 2021-04-14 07:58:52

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/partition-list/discuss/1157797).*

---

#### [Leetcode Problem #86 (*Medium*): Partition List](https://leetcode.com/problems/partition-list/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|head = [1,4,3,2,5,2], x = 3
Output:|[1,2,2,4,3,5]
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2021/01/04/partition.jpg)
>
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`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

The easiest thing to do here is to create separate linked lists for the front and back portions of list we want to return. In order to accomplish that, we should first create some dummy heads (**fdum, bdum**), then create pointers for the current nodes each of the front, back, and main lists (**front, back, curr**).

Then we can simply iterate through the main list and stitch together each node to either **front** or **back**, depending on the node's value.

Once we reach the end, we just need to stitch together the two sub-lists, making sure to cap off the end of **back**, and then **return** our new list, minus the dummy head.

![Visual 1](https://i.imgur.com/X5semXh.png)

---

#### ***Implementation:***

There are only minor differences between the code of all four languages.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var partition = function(head, x) {
    let fdum = new ListNode(0), bdum = new ListNode(0),
        front = fdum, back = bdum, curr = head
    while (curr) {
        if (curr.val < x)front.next = curr, front = curr
        else back.next = curr, back = curr
        curr = curr.next
    }
    front.next = bdum.next, back.next = null
    return fdum.next
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        fdum, bdum = ListNode(0), ListNode(0)
        front, back, curr = fdum, bdum, head
        while curr:
            if curr.val < x:
                front.next = curr
                front = curr
            else:
                back.next = curr
                back = curr
            curr = curr.next
        front.next, back.next = bdum.next, None
        return fdum.next
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode fdum = new ListNode(0), bdum = new ListNode(0),
                 front = fdum, back = bdum, curr = head;
        while (curr != null) {
            if (curr.val < x) {
                front.next = curr;
                front = curr;
            } else {
                back.next = curr;
                back = curr;
            }
            curr = curr.next;
        }
        front.next = bdum.next;
        back.next = null;
        return fdum.next;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode *fdum = new ListNode(0), *bdum = new ListNode(0),
                 *front = fdum, *back = bdum, *curr = head;
        while (curr) {
            if (curr->val < x) front->next = curr, front = curr;
            else back->next = curr, back = curr;
            curr = curr->next;
        }
        front->next = bdum->next, back->next = nullptr;
        return fdum->next;
    }
};
```