# Partitioning a linked list around a given value and If we don’t care about making the elements of the list “stable” ### Problem Statement

In this problem, we will be given a linked list and an integer X. We need to partition the linked list around this integer X such that all elements that are less than X should occur before all elements having a value greater than or equal to X.

### Problem Statement understanding:

To understand this problem statement, let us learn programming languages online and take an example.

If the given linked list is: and X = 5

• Here, X = 5 so, nodes with data less than X are: 1,2,3.
• Nodes with data greater than or equal to X are: 5,8,12.
• We need to keep 1,2,3 before 5,8,12.
• Remember that the order of elements does not matter to us as long as the criteria are satisfied, i.e., elements having a value less than X should be before the elements with a value greater than or equal to X.
• So, the final output will be 1→2→3→5→8→12→NULL

Let us take another example:
If the linked list is 9→1→10→27→42→2→NULL and X = 10

• As explained in the above example, similarly, the output linked list after partitioning the linked list around X = 10 will be: 1→9→2→10→27→42→NULL

Note: The order of the elements does not matter, i.e., in the final linked list, the elements smaller than X should be before the elements greater than or equal to X. The order of the occurrence of the elements in the final linked list need not be the same as the order of occurrence in the initial given linked list. We can change the order of occurrence of elements as long as the main condition is satisfied.

Also, multiple correct outputs are possible for this problem statement.

Now let’s have a look at some helpful observations.

• We need to separate the nodes with values less than X from those with values greater than or equal to X.
• The order of occurrence of nodes does not matter to us.
• Multiple correct solutions exist for this problem.

### Approach

• Here, we will keep track of two pointers i.e., head and tail pointers of the list
• When we encounter an element that is less than X, we will insert it before the head and update the head pointer.
• When we encounter an element greater than or equal to X, we will insert it after the tail node and will update the tail node.

### Algorithm

• Initialize two pointers named current and tail with the starting node of the original linked list.
• Loop in the linked list using this pointer current, starting from first to the last node, and store the next pointer of the current node in another variable before inserting the current node before head or after tail.
• If the current node has a value less than X, insert it before head and update the head.
• If the current node has a value greater than or equal to X, insert it after the tail and update the tail pointer.
• Update the current node with the next pointer stored in step 2.
• After the loop ends, make the next pointer of the tail node point to NULL to avoid the cycle in the newly created list.

### Dry Run   ### Code Implementation

```#include<stdio.h>
#include<stdlib.h>

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

// A utility function to create a new node
Node *newNode(int data)
{
struct Node* new_node = new Node;
new_node->data  = data;
new_node->next = NULL;
return new_node;
}

// Function to make a new list(using the existing
// nodes) and return head of new list.
struct Node *partition(struct Node *head, int x)
{
/* Let us initialize start and tail nodes of
new list */
struct Node *tail = head;

// Now iterate original list and connect nodes
Node *curr = head;
while (curr != NULL)
{
struct Node *next = curr->next;
if (curr->data < x)
{
/* Insert node at head. */
}

else // Append to the list of greater values
{
/* Insert node at tail. */
tail->next = curr;
tail = curr;
}
curr = next;
}
tail->next = NULL;

// The head has changed, so we need
// to return it to the user.
}

/* Function to print linked list */
void printList(struct Node *head)
{
struct Node *temp = head;
while (temp != NULL)
{
printf("%d  ", temp->data);
temp = temp->next;
}
}

// Driver program to run the case
int main()
{
/* Start with the empty list */
struct Node* head = newNode(3);

int x = 5;
return 0;
}
```
```#include<bits stdc++.h="">
using namespace std;
class Node
{
public:
int data;
Node* next;
Node(int x){
data = x;
next = NULL;
}
};

Node *partition(Node *head, int x)
{
/* initialize current and tail nodes of new list
as discussed in step 1*/
Node *tail = head;

Node *curr = head;
while (curr != NULL)
{
Node *next = curr->next;
if (curr->data < x) // left partition
{
/* Insert node before head if current node data is
less than given value of X */
head = curr; // update the head node
}

else // right partition
{
/* Insert node after tail node */
tail->next = curr;
tail = curr; // update the tail node
}
curr = next;
}
tail->next = NULL; // make next of tail node as NULL to
// avoid cycles in newly created list

// return changed head
}

void printList(struct Node *head)
{
Node *temp = head;
while (temp != NULL)
{
printf("%d  ", temp->data);
temp = temp->next;
}
}

int main(void)
{
Node* head = NULL;
head = new Node(3);
head->next = new Node(12);
head->next->next = new Node(1);
head->next->next->next = new Node(5);
head->next->next->next->next = new Node(8);
head->next->next->next->next->next = new Node(2);

Node *tmp = partition(head,5);
printList(tmp);
return 0;
}
```
```class Partition
{

static class Node
{
int data;
Node next;
}
static Node newNode(int data)
{
Node new_node = new Node();
new_node.data = data;
new_node.next = null;
return new_node;
}
// Function to make a new list
// (using the existing nodes) and
// return head of new list.
static Node partition(Node head, int x)
{
/* Let us initialize start and tail nodes of
new list */
Node tail = head;

// Now iterate original list and connect nodes
Node curr = head;
while (curr != null)
{
Node next = curr.next;
if (curr.data < x)
{
/* Insert node at head. */
}

else // Append to the list of greater values
{
/* Insert node at tail. */
tail.next = curr;
tail = curr;
}
curr = next;
}
tail.next = null;

// The head has changed, so we need
// to return it to the user.
}
static void printList(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
}
// Driver code
public static void main(String[] args)
{
/* Start with the empty list */
Node head = newNode(3);

int x = 5;
}
}
```
```class Node:
def __init__(self, data):
self.data = data
self.next = None

def newNode(data):
new_node = Node(data)
new_node.data = data
new_node.next = None
return new_node

# Function to make a new list
# (using the existing nodes)
# and return head of new list.

# Let us initialize start and
# tail nodes of new list

# Now iterate original list
# and connect nodes
while (curr != None):
next = curr.next
if (curr.data < x):

# Insert node at head.

else:

# Append to the list of greater values
# Insert node at tail.
tail.next = curr
tail = curr

curr = next

tail.next = None

# The head has changed, so we need
# to return it to the user.

# Function to print linked list
while (temp != None):
print(temp.data, end = " ")
temp = temp.next

# Driver Code
if __name__=='__main__':

x = 5