Partitioning a linked list around a given value
Partitioning a linked list around a given value
In this problem, we are given a linked list and a value k. We need to partition the given linked list so that all nodes less than k come first, then all nodes that are equal to k, and finally nodes that are greater than k. Also, we need to preserve the order of nodes same as the original list.
Example:
Input:
2 -> 4 -> 5 -> 4 -> 3 -> 2 -> 3 k = 3
Output:
2 -> 2 -> 3 -> 3 -> 4 -> 5 -> 4
Input:
1 -> 3 -> 2 -> 5 -> 3 -> 6 k = 4
Output:
1 -> 3 -> 2 -> 3 -> 5 -> 6
Method:
In this method, we will take three list and initialize their first and last nodes as given below:
- The linked list contains the node which has a smaller value than k.
- The linked list contains the node which has an equal value to k.
- The linked list contains the node which has a greater value than k.
After this, we traverse the given linked list. If a node has a smaller value than k, we will append that node at the end of the smaller linked list. If the node value is equal to k, we will append it at the end of the equal linked list, and if a value is greater than k, we will append that node at the end of the greater linked list. Finally, we will concatenate these three linked lists to display the output.
C Program to partitioning a linked list around a given value:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node * next;
};
struct node * start = NULL;
// For inserting the elements in the linked list
void add(int item)
{
struct node * t, * p;
t = (struct node *)malloc( sizeof( struct node ));
if(start == NULL)
{
start = t;
start -> info = item;
start -> next = NULL;
return;
}
else
{
struct node * p = start;
while(p -> next != NULL)
{
p = p -> next;
}
p -> next = t;
p = p -> next;
p -> info = item;
p -> next = NULL;
}
}
// For partitioning a linked list around a given value
struct node * partition(struct node * temp, int k)
{
struct node * smallerFirst = NULL, * smallerLast = NULL;
struct node * equalFirst = NULL, * equalLast = NULL;
struct node * greaterFirst = NULL, * greaterLast = NULL;
while(temp != NULL)
{
if(temp -> info < k)
{
if(smallerFirst == NULL)
{
smallerFirst = temp;
smallerLast = smallerFirst;
}
else
{
smallerLast -> next = temp;
smallerLast = smallerLast -> next;
}
}
else if( temp -> info == k)
{
if(equalFirst == NULL)
{
equalFirst = temp;
equalLast = equalFirst;
}
else
{
equalLast -> next = temp;
equalLast = equalLast -> next;
}
}
else
{
if(greaterFirst == NULL)
{
greaterFirst = temp;
greaterLast = greaterFirst;
}
else
{
greaterLast -> next = temp;
greaterLast = greaterLast -> next;
}
}
temp = temp -> next;
}
// For fixing the end of greater linked list
if(greaterLast != NULL)
greaterLast -> next = NULL;
// Connect three lists
// If smaller list is empty
if (smallerFirst == NULL)
{
if (equalFirst == NULL)
return greaterFirst;
equalLast -> next = greaterFirst;
return equalFirst;
}
// If smaller list is not empty
// and equal list is empty
if (equalFirst == NULL)
{
smallerLast -> next = greaterFirst;
return smallerFirst;
}
// If both smaller and equal list
// are non-empty
smallerLast -> next = equalFirst;
equalLast -> next = greaterFirst;
return smallerFirst;
}
// To display the elements of the linked list
void traverse(struct node * t)
{
if(t == NULL)
{
printf(" Linked list is empty\n");
}
while(t -> next != NULL)
{
printf("%d -> ",t -> info);
t = t -> next;
}
printf("%d\n",t -> info);
}
// Driver Function
int main()
{
int k;
printf("Enter the value of k:");
scanf("%d",&k);
add(2);
add(4);
add(5);
add(4);
add(3);
add(2);
add(3);
printf("Given Linked List: \n");
traverse(start);
start = partition(start, k);
printf("Linked List After partitioning: \n");
traverse(start);
return 0;
}
Output:
