#### 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:
def partition(self, head, x):
if head == None or head.next == None: # Special cases
return head
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
while head != None:
if head.val < x:
less.next = ListNode(head.val)
less = less.next
else:
more.next = ListNode(head.val)
more = more.next
head = head.next # We always go to the next node.
less.next = head_more.next # Combine the two lists.
return head_less.next # Remember to skip the dummy node.
```

**Complexity Analysis**

- Time complexity : $$O(n)$$. We iterate through the list exactly once, and the concatenation procedure is in constant time.

- Space complexity : $$O(n)$$. In the algorithm we generate a copy of each node in the list. Because we have $$2n$$, this reduces to $$O(n)$$ space. This algorithm can be modified to use $$n$$ space by mutating the list in place.