  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Partitioning a linked list around a given value and keeping the original order

Last Updated on November 25, 2022 by Prepbytes This article will discuss the coding problem “partition a linked list around a given value” and its solution. Before jumping into the problem statement and approach you need to know about the linked list data structure. Let us understand the problem statement of partition a linked list around a given value. For a better understanding.

## Partitioning a linked list around a given value

In this problem, given a linked list and a value X, we are required to partition it such that all nodes less than X come before nodes greater than or equal to x.

Note: You should maintain the original relative order of the nodes in each of the two partitions.

Let’s understand the problem statement with the help of examples.

If the given linked list is: It means that we have to move all nodes smaller than 3 before the nodes have values greater than or equal to 3. Also, while partitioning the linked list around value 3, the original relative order of the nodes in each of the two partitions should be maintained.

So our final resultant linked list after partitioning will look like this: This statement maintains the original relative order of the nodes in each of the two partitions implies that while partitioning, the nodes in each of the two partitions should be in the same order as they are present in the original linked list.

• From the above-linked list, we can see that 1, 2, and 2 will come in the first partition(nodes smaller than X) and 4, 3, and 7 will come in the second partition(nodes greater than or equal to X).
• If we carefully compare the resultant linked list and the original linked list we can clearly see that 1, 2, and 2, the nodes of the first partition are in the same order in the resultant list as they were in the original linked list (2 is occurring after 1 and another 2 is occurring after 2). Similarly, the nodes of the second partition 4, 3, and 7 are also in the same order as they were in the original linked list (3 is occurring after 4 and another 5 is occurring after 3).

Explanation: In the resultant linked list, first there will be the elements of the first partition (elements or nodes smaller than X) and then there will be the elements of the second partition (elements greater than or equal to X). Also, both partitions will preserve the order from the original linked list.

Now I think from the above example the problem is clear, we will have to now think of how we can approach this problem.

## Approach to partition a linked list around a given value

As we need all the nodes having a value smaller than X before nodes having a value greater than or equal to X, so we will have to divide the original linked list into two sections:

• A list of nodes with values less than X and,
• A list of nodes with values higher than or equal to X.

Then, after diving into the original linked list, we’ll use pointers to stitch them back together after the division such that all the nodes having smaller value than X comes before nodes having a greater value equal to X.

The algorithm in brief:

We will traverse the original linked list as normal, and we will select in which linked list a node should belong to based on its value.

• If a node’s value is less than X, it will be appended to the low-container list, which keeps track of nodes with values less than X.
• Otherwise, it will be appended to the high-container list, which keeps track of nodes with values greater than or equal to X.

Finally, after traversing, we’ll sew the end node of the first linked list (the low-container list) to the head node of our second list (the high-container list). This way, we can maintain the order of elements in the list.

After the complete traversal of the original linked list, the low-container list will have all the nodes having value smaller than X, while the high-container list will have all the nodes having values greater than or equal to X.

A few buffers will be required to maintain track of the partitioned lists.

• less: A pointer that will help us in linking every node with the value lower than X together, this way we will get the low-container list. It will act as an iterator for the low-container linked list.
• more: A pointer which will help us in linking every node with the value higher or equal to the X together, this way we will get the high-container list. It will act as an iterator for the high-container linked list.

## Algorithm to partition a linked list around a given value

• Check if head == NULL, If true, return NULL.
• Begin iterating the original linked list. We’ll try to make two distinct linked lists (low-container list and high-container list) out of the original linked list by just changing the links.
• While traversing the original linked list:
• If a node is having value smaller than X, it will get appended to the end of low-container list.
• If a node is having value greater than or equal to X, it will get appended to the end of high-container list.
• Once the traversal of the original linked list is over, the low-container list will be a list having all the nodes with values smaller than X and the high-container list will contain all the nodes from the original list having values greater than or equal to X.
• The heads of the two linked lists above will both point to the first node of their own lists.
• Finally, all that remains is to stitch the lists back together. The low-container linked list’s last node should point to the head of the high-container linked list.
• We will return the head of high-container list if the low-container list does not exist (the original linked list does not contains any nodes with a value less than X) and if the low-container list exists we will make new_Head point to head of low-container(low_Head) and will return new_Head.

### Dry Run of partition a linked list around a given value   ## Code Implementation of partition a linked list around a given value

```#include
using namespace std;

// Structure of a node
struct node{
int val;
struct node* next;
node(int x){
val=x;
next=NULL;
}
};

// Return pointer to the produced list.
struct node* orderOfList(struct node* head,int x){
// return NULL if the linked list is empty

// Head of the modified list
// Head of low-container list partition
// Head of high-container list partition
// Itearator of low-container list.
struct node* less = NULL;
//  Iterator of high-container list.
struct node* more = NULL;

// traverse through the list.
/* If the node's value is less than x,
it should go in low-container.

If we haven't set the head of low-container
// and also point the iterator to the beginning.
}else{
/* If the low_Head is already initialized, we are required to point the iterator to point to this node*/
}

}else{

/* initialize if the head of the high-container has not been initialized yet.
and point the 'more' iterator to the beginning
}else{
point the next field of last node in this list to head*/
// updating the iterator
}
}
// Update the iterator of the original list.
}
/* If the first partition of the linked list(low-container) is empty, we just return the high_Head.
Also point the last node's next to NULL.*/
more->next = NULL;
}else{
/* if the low_head list exists
/* last node of the low-container should
more->next = NULL;
}
}
}

// To traverse through the linked list
cout<val<<" ";
}
}
int main() {

struct node* head = new node(1);
int x = 3;

return 0;
}
```
```
```
```
```
```
```

Output
1→2→2→4→3→7

Time Complexity of partition a linked list around a given value: O(N) – we are traversing through the original linked list and only creating 2 linked lists out of it.

**Conclusion**

This article discussed the “partition a linked list around a given value” problem, and we have discussed the most efficient approach with the help of a dry run. We hope this article will enhance your knowledge. This problem is interesting as well as important from the interviewee’s point of view. If you want to solve more questions on Linked List, which is curated by our expert mentors at PrepBytes, you can follow this link Linked List.

## FAQs related to partition a linked list around a given value

**1. What is a linked list?**
A linked list is a linear data structure. It is a collection of nodes and each node contains two parts, the first is data and the other one is a pointer to the next node.

**2. What is the main difference between a singly linked list and a doubly linked list?**
The major difference between a singly linked list and a doubly linked list is a singly linked list is unidirectional whereas the doubly linked list is bidirectional.