Partition Linked List

/* Partition a linked list around a value x, 
such that all nodes less than x come before all nodes greater than or equal to x. */

#include <iostream>

struct node{
int data;
node * next;
};

node * partitionLinkedListByValue(node * head, int x){
node * smaller = new node();
node * greater = new node();
node * head1 = smaller;
node * head2 = greater;
while (head != nullptr) {
if (head->data < x) {
smaller->next = head;
smaller = smaller->next;
} else {
greater->next = head;
greater = greater->next;
}
head = head->next;
}
smaller->next = head2->next;
smaller = head1->next;
delete head1;
delete head2;
return smaller;
}