## DEV Community is a community of 847,300 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Solution: Partition List

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

#### Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

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. #### Implementation:

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

#### Javascript Code:

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

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

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

``````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;
}
};
``````

## Discussion (3) Aaron Reese

In js at least I would use array.filter into two new arrays and then use the spread operator to merge the arrays. 4 lines of clean code, or 1 line of horrible code if you are a smart-arse Dev 😁 seanpgallivan

Unfortunately, the input is a linked list, not an array. It's shown as an array in the example just to make it easier to read.