In this tutorial, i will show you how to partition a linked list using a value x such that all nodes less than `x`

come before nodes greater than or equal to `x`

and we are to preserve the original relative order of the nodes in each of the two partitions.

This question is posted in leetcode here: https://leetcode.com/problems/partition-list/ and the i have used recursion to solve it because i needed to take advantage of the power of backtracking to be able to preserve the original relative order of the nodes; not just that, just continue reading for the final idea to preserve the order of the nodes.

So basically what i have done in the code below is to create two new nodes NH1 and NH2. I first of all traverse the given linked list from the head node to the last node using recursion – of course the base case is when i reach NULL, then during backtracking i check the value of the current node against the given value x; if x > currentnodes->value, i create a new node, assign the value of the currentnode to the new node and then insert the new node at the head position of NH1 otherwise i insert the new node at the head position of NH2. Inserting the new node at the head position of either NH1 or NH2 is the final idea to preserve the order of the nodes in each of the two partitions. Finally i merge the last node of NH1 to the head node of NH2 and that’s it.

### Implementation in c

```
struct ListNode {//node structure
int val;
struct ListNode *next;
};
struct ListNode *NH1 = NULL;//create node for holding values lesser than 3
struct ListNode *NH2 = NULL;//create node for holding values greater than 3
struct ListNode* partition(struct ListNode** head, int x){
static int countt = 0, btractCnt = 0;
if(*head == NULL){
return 0;
}else{
if(countt == 0){//get count of nodes in given list
struct ListNode *temp = *head;
while(temp != NULL){
temp = temp->next;
countt++;
}
}
struct node *H = (*head)->next;
partition(&H, x);//recurse
btractCnt++;
if(x > (*head)->val){//compare x against given list nodes val
struct ListNode *newnode = malloc(sizeof(struct ListNode));
newnode->val = (*head)->val;
if(NH1 == NULL){
newnode->next = NULL;
NH1 = newnode;
}else{
newnode->next = NH1;
NH1 = newnode;
}
}else{
struct ListNode *newnode = malloc(sizeof(struct ListNode));
newnode->val = (*head)->val;
if(NH2 == NULL){
newnode->next = NULL;
NH2 = newnode;
}else{
newnode->next = NH2;
NH2 = newnode;
}
}
if(btractCnt == countt){//done comparing x against given list nodes val
struct ListNode *temp1;//temporary node for traversal
struct ListNode *Hp;//create heap pointer for NH1
Hp = temp1 = NH1;//initialize temp node and head pointer
while(temp1->next != NULL)//get to the lastnode of NH1
temp1 = temp1->next;
temp1->next = NH2;//merge the two new linked list
NH1 = Hp;//mark the head node after merge
}
}
return 0;
}
void Print_List(struct ListNode **head){
struct ListNode *temp = *head;
while(temp != NULL){
printf("%d ", temp->val);
temp = temp->next;
}
free(temp);
return 0;
}
int main(){
//create the list
struct ListNode *n1,*n2,*n3,*n4,*n5,*n6;
n1 = malloc(sizeof(struct ListNode));
n2 = malloc(sizeof(struct ListNode));
n3 = malloc(sizeof(struct ListNode));
n4 = malloc(sizeof(struct ListNode));
n5 = malloc(sizeof(struct ListNode));
n6 = malloc(sizeof(struct ListNode));
//assign values to nodes
n1->val = 1;
n2->val = 4;
n3->val = 3;
n4->val = 2;
n5->val = 5;
n6->val = 2;
n6->next = NULL;
//connect nodes
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = n6;
partition(&n1, 3);//partition list by the value 3
Print_List(&NH1);//print partitioned list
}
```