Introduction
This article will discuss the problem “Partitioning a linked list around a given value and keeping the original order” and its solution. Before jumping into the details of the problem and approach to solve it, you need to know about the linked list data structure.
Now, let’s understand the problem. In this problem, a linked list and a value ‘x’ is given, and we have to partition the linked list such a way that all the nodes with values less than ‘x’ come first, then the nodes having values equal to ‘x’ and then, at last, the nodes with values greater than ‘x’. And, we have to do this partitioning along with preserving the original order of nodes in the three partitions.
Let’s understand this problem of partitioning a linked list by taking an example.
Assume the given linked list is : 1 -> 4 -> 5 -> 9 -> 8 -> 5 -> 2
and given x = 5
We can see that there are three nodes having values less than 5, which arranged in the original order are as follows:
1 -> 4 -> 2
There are two nodes having values equal to 5, which arranged in the original order are as follows:
5 -> 5
We can see that there are two nodes having values less than 5, which arranged in the original order are as follows:
9 -> 8
So, output of “partitioning a linked list” for the linked list and ‘x’ given in the example should be: 1 -> 4 -> 2 -> 5 -> 5 -> 9 -> 8
Recommended Topic, Floyds Algorithm
Brute Force Approach
In this problem “Partitioning a linked list around a given value”, we have to partition the given linked list such that all the nodes with values less than ‘x’ come first, then the nodes having values equal to ‘x’ and then, at last, the nodes with values greater than ‘x’ and also the original order in the three partitions remain same. Here ‘x’ is the given value around which partitioning of the linked list is to be done.
So, we can create three different linked lists for storing the nodes having values less than ‘x’, equal to ‘x’, and greater than ‘x’. The solution is to traverse the given linked list. The following three cases will arise:
- The value of the current node will be less than ‘x’ - In this case, add a node to the linked list, storing the nodes having values less than ‘x’.
- The value of the current node will be equal to the ‘x’ - In this case, add a node to the linked list, storing the nodes having values equal to ‘x’.
- The value of the current node will be greater than ‘x’ - In this case, add a node to the linked list, storing the nodes having values greater than ‘x’.
After traversing through all the nodes of the given linked list, concatenate the three linked lists that have been created in the following order:
First, the linked list which has stored the nodes with values less than ‘x’, then the one which has stored the nodes with values equal to ‘x’, and at last the one which has stored the nodes with values greater than ‘x’.
Algorithm
Step 1. Create a class ‘Node’ for creating the linked lists.
Step 2. Then create the function “partition()” for partitioning a linked list around a given value, which will take two inputs - the pointer pointing to the given linked list's head node and the given value ‘x’.
Inside the function, create six node pointers for pointing to the head node and last node of each of the three linked lists that we are creating to separate the nodes with values less than ‘x’, equal to ‘x’, and greater than ‘x’.
Step 3. Now create a node pointer “curr_node” to point to the current node of the linked list and, starting from the head node, traverse all the nodes of the linked list using this “curr_node” pointer and a “while loop”. While traversing the linked list, if the current node's value is less than ‘x’, create a new node with the same value as the current node and add it to the linked list storing the nodes with values less than ‘x’. Similarly, if the current node's value is equal to or greater than ‘x’, create new nodes and add them to the respective linked list.
Step 4. When “curr_node” becomes “NULL", i.e., after traversing all the nodes, concatenate the three linked lists using their head and last node pointers in the required order as explained in the above “efficient approach” section.
Step 5. Finally, after concatenating the linked list, return its head.
C++ code
#include <bits/stdc++.h>
using namespace std;
// Class for creating nodes of the linked list
class Node {
public:
int data;
Node* next;
Node(int val) {
this->data = val;
this->next = NULL;
}
};
// Function to print the linked list
void printList(Node* head)
{
Node* curr_node = head;
while(curr_node != NULL)
{
if(curr_node->next == NULL) {
cout<< curr_node->data <<" ";
}
else {
cout<<curr_node->data<<" -> ";
}
curr_node = curr_node->next;
}
cout<<endl;
}
// Function for partitioning a linked list around a given value
Node* partition(Node* head, int x)
{
// Head node of the linked list for storing nodes with values less than x
Node* less = NULL;
// Last node of the linked list for storing nodes with values less than x
Node* less_last = NULL;
// Head node of the linked list for storing nodes with values equal to x
Node* equal = NULL;
// Last node of the linked list for storing nodes with values equal to x
Node* equal_last = NULL;
// Head node of the linked list for storing nodes with values greater than x
Node* greater = NULL;
// Last node of the linked list for storing nodes with values greater than x
Node* greater_last = NULL;
Node* curr_node = head;
while(curr_node != NULL)
{
if(curr_node->data < x)
{
if(less == NULL)
{
less = new Node(curr_node->data);
less_last = less;
}
else {
less_last->next = new Node(curr_node->data);
less_last = less_last->next;
}
}
else if(curr_node->data == x)
{
if(equal == NULL)
{
equal = new Node(curr_node->data);
equal_last = equal;
}
else {
equal_last->next = new Node(curr_node->data);
equal_last = equal_last->next;
}
}
else {
if(greater == NULL)
{
greater = new Node(curr_node->data);
greater_last = greater;
}
else {
greater_last->next = new Node(curr_node->data);
greater_last = greater_last->next;
}
}
curr_node = curr_node->next;
}
// Concatenate the three lists in order
// If list with less value nodes is empty
if (less == NULL)
{
if (equal == NULL)
return greater;
equal_last->next = greater;
return equal;
}
/*
If the list with less value nodes is not empty
and list with equal value nodes is empty
*/
if (equal == NULL)
{
less_last->next = greater;
return less;
}
// If both lists with less and equal values are non-empty
less_last->next = equal;
equal_last->next = greater;
return less;
}
int main()
{
Node* head = new Node(1);
head->next = new Node(4);
head->next->next = new Node(5);
head->next->next->next = new Node(9);
head->next->next->next->next = new Node(8);
head->next->next->next->next->next = new Node(5);
head->next->next->next->next->next->next = new Node(2);
cout<<"The given linked list is: "<<endl;
printList(head);
int x =5;
// Call the function for partitioning a linked list around a given value
head = partition(head, x);
cout<<"The linked list after partition is: "<<endl;
printList(head);
}
Output:
The given linked list is:
1 -> 4 -> 5 -> 9 -> 8 -> 5 -> 2
The linked list after partition is:
1 -> 4 -> 2 -> 5 -> 5 -> 9 -> 8 Algorithm Complexity: Algorithm Complexity
Time Complexity: O(N)
In the function “partition()” created for partitioning a linked list, we have created a “while loop” to one by one traverse all the nodes of the given linked list. So, the time complexity is O(N), where ‘N’ is the number of nodes in the given linked list.
Space Complexity: O(N)
In the function “partition()” created for partitioning a linked list, We have created new linked lists for storing the nodes separately according to their value with respect to ‘x’. The total number of new nodes created is ‘N’, where ‘N’ is the number of nodes in the given linked list. So, the space complexity is O(N).
84+ registered