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;
}
}
else // Append to the list of greater values
{
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 program to run the case
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;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C++ program to partition a linked list around a
// given value.
#include <stdio.h>
#include <stdlib.h>
/* Link list Node */
typedef struct Node {
int data;
struct Node* next;
} Node;
// A utility function to create a new node
Node* newNode(int data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = data;
new_node->next = NULL;
return new_node;
}
// Function to make two separate lists and return
// head after concatenating
Node* partition(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.*/
Node *smallerHead = NULL, *smallerLast = NULL;
Node *greaterLast = NULL, *greaterHead = NULL;
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;
}
}
else // Append to the list of greater values
{
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(Node* head)
{
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 */
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;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to partition a
// linked list around a given value.
class GfG {
/* Link list Node */
static class Node {
int data;
Node next;
}
// A utility function to create a new node
static Node newNode(int data)
{
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
static Node partition(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.*/
Node smallerHead = null, smallerLast = null;
Node greaterLast = null, greaterHead = null;
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;
}
}
else // Append to the list of greater values
{
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 */
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(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);
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program to partition a # linked list around a given value. # Link list Node class Node: def __init__(self): self.data = 0 self.next = None # A utility function to create a new node def newNode( data): new_node = Node() new_node.data = data new_node.next = None return new_node # Function to make two separate lists and return # head after concatenating def partition( head, 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. smallerHead = None smallerLast = None greaterLast = None greaterHead = None equalHead = None equalLast = None # Now iterate original list and connect nodes # of appropriate linked lists. while (head != None) : # If current node is equal to x, append it # to the list of x values if (head.data == x): if (equalHead == None): 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 == None): smallerLast = smallerHead = head else: smallerLast.next = head smallerLast = head else : # Append to the list of greater values if (greaterHead == None) : greaterLast = greaterHead = head else: greaterLast.next = head greaterLast = head head = head.next # Fix end of greater linked list to None if this # list has some nodes if (greaterLast != None) : greaterLast.next = None # Connect three lists # If smaller list is empty if (smallerHead == None) : if (equalHead == None) : return greaterHead equalLast.next = greaterHead return equalHead # If smaller list is not empty # and equal list is empty if (equalHead == None) : 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 def printList(head) : temp = head while (temp != None): print(temp.data ,end= " ") temp = temp.next # Driver code # Start with the empty list 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) x = 3 head = partition(head, x) printList(head) # This code is contributed by Arnab Kundu.
C#
// C# program to partition a
// linked list around a given value.
using System;
public class GfG
{
/* Link list Node */
public class Node
{
public int data;
public Node next;
}
// A utility function to create a new node
static Node newNode(int data)
{
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
static Node partition(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.*/
Node smallerHead = null, smallerLast = null;
Node greaterLast = null, greaterHead = null;
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;
}
}
else // Append to the list of greater values
{
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 */
static void printList(Node head)
{
Node temp = head;
while (temp != null)
{
Console.Write(temp.data + " ");
temp = temp.next;
}
}
// Driver code
public static void Main()
{
/* Start with the empty list */
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);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to partition a
// linked list around a given value.
/* Link list Node */
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// A utility function to create a new node
function newNode(data) {
var 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
function partition(head , 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.
*/
var smallerHead = null, smallerLast = null;
var greaterLast = null, greaterHead = null;
var 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;
}
} else // Append to the list of greater values
{
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 */
function printList(head) {
var temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
}
// Driver code
/* Start with the empty list */
var 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);
var x = 3;
head = partition(head, x);
printList(head);
// This code contributed by aashish1995
</script>
Producción
2 10 4 5 30 50
Complejidad temporal: O(n) donde n es el tamaño de la lista enlazada
Espacio auxiliar: O(1)
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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