# Solution by tanx16

• #### Approach #1 Partitioning (Accepted)

Intuition

We want to move all nodes smaller than \$\$x\$\$ to the front of the list, without disturbing the rest of the nodes. This is equivalent to taking all nodes larger than or equal to \$\$x\$\$ and moving them to the back of the list. Therefore we can traverse the list to partition it into nodes with smaller value than \$\$x\$\$ and larger or equal value to \$\$x\$\$.

Algorithm

Given the linked list, we first create two empty lists to contain the smaller and larger nodes. Let these lists be known as larger and smaller. In order to merge the lists at the end of the procedure, we must also create pointers to keep track of the head of each list.
We iterate through the list. For each node we append it to smaller if the node value is smaller than \$\$x\$\$, and larger otherwise. When we reach the end of the list, we have two linked lists containing the partitioned list. The lists can be combined by appending the larger list to the smaller list, using the pointers we create in the beginning of the procedure. The resulting list is the successfully partitioned list.

Python

``````class Solution:
less = ListNode(None) # Dummy node
more = ListNode(None) # Dummy node
head_more = more # Pointer to keep track of the list head
head_less = less # Pointer to keep track of the list head
less = less.next
else: