Algorithm :

- Take two vectors v1(for collecting node values < x) and v2(for collecting values >= x).
- Traverse through the link list and fill the vectors based on value.
- Now, traverse through the list again and change the node values with the value in v1
- Once done with v1, start filling the value from v2

Complexity : O(N).

```
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
int size=0;
ListNode *temp=head,*start=NULL;
vector<int> before,after;
// Check for corner cases in which list if NULL or number of elements is zero.
if((head==NULL) || (head->next==NULL))
return head;
// Create two vectors(before and after) to store the value less than and greater than x respectively.
while(temp)
{
if(temp->val<x)
before.push_back(temp->val);
else
after.push_back(temp->val);
temp = temp->next;
}
// Start from the beginning and change the value in the original list with the values present in the first vector(before)
temp = head;
size = before.size();
for(int i=0;i<size;i++)
{
temp->val = before[i];
temp = temp->next;
}
// Now update the remaining list pointers with the second vector (after) i.e all value greater thn or equals to x.
size=after.size();
for(int i=0;i<size;i++)
{
temp->val = after[i];
temp = temp->next;
}
return head;
}
};
```