# Partition List – preserve the original relative order of the nodes using c

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;
return 0;
}else{
if(countt == 0){//get count of nodes in given list
while(temp != NULL){
temp = temp->next;
countt++;
}
}

partition(&H, x);//recurse
btractCnt++;
if(x > (*head)->val){//compare x against given list nodes val
struct ListNode *newnode = malloc(sizeof(struct ListNode));
if(NH1 == NULL){
newnode->next = NULL;
NH1 = newnode;
}else{
newnode->next = NH1;
NH1 = newnode;
}
}else{
struct ListNode *newnode = malloc(sizeof(struct ListNode));
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;
}

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
}``````

## lazy bartender problem solution

Daily Coding Problem: Problem #297 [Medium] This problem was asked by Amazon. At a popular bar, each customer…

## Finding Duplicates in a String Using Bitwise Operations – in c/c++

In this tutorial i am going to show you how to find duplicates in a string using bitwise…

## Remove All Occurrences Of An Element From Array In c – Interview Question

Remove All Occurrences Of An Element From Array In c is a tutorial aimed at showing how to…

## Remove Duplicates From Sorted Array In C – Using Two Pointers

Remove Duplicates From Sorted Array In c is a tutorial aimed at showing you how to use two…

## Two Sum With Two Pointers – Interview Question Solution

Two sum with two pointers problem solving technique is a technique where two elements of a sorted array…

## Write A C Program To Move All Zeros To The End Of An Array – Two Pointer Technique Solution

Write a c program to move all zeros to the end of an array is an interview question…