Dada una lista enlazada y un valor x, se divide de manera que todos los Nodes menores que x sean los primeros, luego todos los Nodes con un valor igual a x y finalmente los Nodes con un valor mayor o igual a x. Debe conservarse el orden relativo original de los Nodes en cada una de las tres particiones. La partición debe funcionar en su lugar.
Ejemplos:
Input: 1->4->3->2->5->2->3,
x = 3
Output: 1->2->2->3->3->4->5
Input: 1->4->2->10
x = 3
Output: 1->2->4->10
Input: 10->4->20->10->3
x = 3
Output: 3->10->4->20->10
Para resolver este problema, podemos usar el método de partición de Quick Sort , pero esto no preservaría el orden relativo original de los Nodes en cada una de las dos particiones.
A continuación se muestra el algoritmo para resolver este problema:
- Inicialice el primer y el último Node de las siguientes tres listas vinculadas como NULL.
- Lista enlazada de valores menores que x.
- Lista enlazada de valores iguales a x.
- Lista enlazada de valores mayores que x.
- Ahora itere a través de la lista enlazada original. Si el valor de un Node es menor que x, agréguelo al final de la lista más pequeña. Si el valor es igual a x, entonces al final de la lista igual. Y si un valor es mayor, entonces al final de la lista mayor.
- Ahora concatene tres listas.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to partition a linked list
// around a given value.
#include<bits/stdc++.h>
using namespace std;
// Link list Node
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 two separate lists
// and return head after concatenating
struct Node *partition(struct Node *head,
int x)
{
/* Let us initialize first and last
nodes of three linked lists
1) Linked list of values smaller
than x.
2) Linked list of values equal
to x.
3) Linked list of values greater
than x.*/
struct Node *smallerHead = NULL,
*smallerLast = NULL;
struct Node *greaterLast = NULL,
*greaterHead = NULL;
struct Node *equalHead = NULL,
*equalLast = NULL;
// Now iterate original list and
// connect nodes of appropriate
// linked lists.
while (head != NULL)
{
// If current node is equal to x,
// append it to the list of x values
if (head->data == x)
{
if (equalHead == NULL)
equalHead = equalLast = head;
else
{
equalLast->next = head;
equalLast = equalLast->next;
}
}
// If current node is less than X,
// append it to the list of smaller
// values
else if (head->data < x)
{
if (smallerHead == NULL)
smallerLast = smallerHead = head;
else
{
smallerLast->next = head;
smallerLast = head;
}
}
// Append to the list of greater values
else
{
if (greaterHead == NULL)
greaterLast = greaterHead = head;
else
{
greaterLast->next = head;
greaterLast = head;
}
}
head = head->next;
}
// Fix end of greater linked list to
// NULL if this list has some nodes
if (greaterLast != NULL)
greaterLast->next = NULL;
// Connect three lists
// If smaller list is empty
if (smallerHead == NULL)
{
if (equalHead == NULL)
return greaterHead;
equalLast->next = greaterHead;
return equalHead;
}
// If smaller list is not empty
// and equal list is empty
if (equalHead == NULL)
{
smallerLast->next = greaterHead;
return smallerHead;
}
// If both smaller and equal list
// are non-empty
smallerLast->next = equalHead;
equalLast->next = greaterHead;
return smallerHead;
}
// 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 code
int main()
{
// Start with the empty list
struct Node* head = newNode(10);
head->next = newNode(4);
head->next->next = newNode(5);
head->next->next->next = newNode(30);
head->next->next->next->next =
newNode(2);
head->next->next->next->next->next =
newNode(50);
int x = 3;
head = partition(head, x);
printList(head);
return 0;
}
Producción:
2 10 4 5 30 50
Complejidad de tiempo: O(n) donde n es el tamaño de la lista enlazada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
¡Consulte el artículo completo sobre cómo dividir una lista vinculada en torno a un valor dado y mantener el orden original para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA