Dada una lista enlazada y un valor x, divida una lista enlazada en torno a un valor x, de modo que todos los Nodes menores que x estén antes que todos los Nodes mayores o iguales a x. Si x está dentro de la lista, los valores de x solo necesitan estar después de los elementos menores que x (ver más abajo). El elemento de partición x puede aparecer en cualquier parte de la «partición derecha»; no es necesario que aparezca entre las particiones izquierda y derecha.
Problema similar: dividir una lista vinculada en torno a un valor dado y mantener el orden original
Ejemplos:
Input : 3 -> 5 -> 10 -> 2 -> 8 -> 2 -> 1
x = 5
Output : 1-> 2-> 2-> 3-> 5-> 10-> 8
Si no nos importa hacer que los elementos de la lista sean «estables», entonces podemos reorganizar los elementos haciendo crecer la lista en la cabeza y la cola.
En este enfoque, comenzamos una lista «nueva» (usando los Nodes existentes). Los elementos más grandes que el elemento pivote se colocan en la cola y los elementos más pequeños se colocan en la cabeza. Cada vez que insertamos un elemento, actualizamos la cabeza o la cola.
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 a new list(using the existing
// nodes) and return head of new list.
struct Node *partition(struct Node *head, int x)
{
/* Let us initialize start and tail nodes of
new list */
struct Node *tail = head;
// Now iterate original list and connect nodes
Node *curr = head;
while (curr != NULL)
{
struct Node *next = curr->next;
if (curr->data < x)
{
/* Insert node at head. */
curr->next = head;
head = curr;
}
else // Append to the list of greater values
{
/* Insert node at tail. */
tail->next = curr;
tail = curr;
}
curr = next;
}
tail->next = NULL;
// The head has changed, so we need
// to return it to the user.
return head;
}
/* 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(3);
head->next = newNode(5);
head->next->next = newNode(8);
head->next->next->next = newNode(2);
head->next->next->next->next = newNode(10);
head->next->next->next->next->next = newNode(2);
head->next->next->next->next->next->next = newNode(1);
int x = 5;
head = partition(head, x);
printList(head);
return 0;
}
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 a new list
// (using the existing nodes) and
// return head of new list.
static Node partition(Node head, int x)
{
/* Let us initialize start and tail nodes of
new list */
Node tail = head;
// Now iterate original list and connect nodes
Node curr = head;
while (curr != null)
{
Node next = curr.next;
if (curr.data < x)
{
/* Insert node at head. */
curr.next = head;
head = curr;
}
else // Append to the list of greater values
{
/* Insert node at tail. */
tail.next = curr;
tail = curr;
}
curr = next;
}
tail.next = null;
// The head has changed, so we need
// to return it to the user.
return head;
}
/* 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(3);
head.next = newNode(5);
head.next.next = newNode(8);
head.next.next.next = newNode(2);
head.next.next.next.next = newNode(10);
head.next.next.next.next.next = newNode(2);
head.next.next.next.next.next.next = newNode(1);
int x = 5;
head = partition(head, x);
printList(head);
}
}
// This code is contributed by prerna saini
Python3
# Python3 program to partition a # linked list around a given value. import math # Link list Node class Node: def __init__(self, data): self.data = data self.next = None # A utility function to create a new node def newNode(data): new_node = Node(data) new_node.data = data new_node.next = None return new_node # Function to make a new list # (using the existing nodes) # and return head of new list. def partition(head, x): # Let us initialize start and # tail nodes of new list tail = head # Now iterate original list # and connect nodes curr = head while (curr != None): next = curr.next if (curr.data < x): # Insert node at head. curr.next = head head = curr else: # Append to the list of greater values # Insert node at tail. tail.next = curr tail = curr curr = next tail.next = None # The head has changed, so we need # to return it to the user. return head # Function to print linked list def printList(head): temp = head while (temp != None): print(temp.data, end = " ") temp = temp.next # Driver Code if __name__=='__main__': # Start with the empty list head = newNode(3) head.next = newNode(5) head.next.next = newNode(8) head.next.next.next = newNode(2) head.next.next.next.next = newNode(10) head.next.next.next.next.next = newNode(2) head.next.next.next.next.next.next = newNode(1) x = 5 head = partition(head, x) printList(head) # This code is contributed by AbhiThakur
C#
// C# program to partition a linked list
// around a given value.
using System;
class GfG
{
/* Link list Node */
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 a new list
// (using the existing nodes) and
// return head of new list.
static Node partition(Node head, int x)
{
/* Let us initialize start and
tail nodes of new list */
Node tail = head;
// Now iterate original list
// and connect nodes
Node curr = head;
while (curr != null)
{
Node next = curr.next;
if (curr.data < x)
{
/* Insert node at head. */
curr.next = head;
head = curr;
}
else // Append to the list of greater values
{
/* Insert node at tail. */
tail.next = curr;
tail = curr;
}
curr = next;
}
tail.next = null;
// The head has changed, so we need
// to return it to the user.
return head;
}
/* 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(String[] args)
{
/* Start with the empty list */
Node head = newNode(3);
head.next = newNode(5);
head.next.next = newNode(8);
head.next.next.next = newNode(2);
head.next.next.next.next = newNode(10);
head.next.next.next.next.next = newNode(2);
head.next.next.next.next.next.next = newNode(1);
int x = 5;
head = partition(head, x);
printList(head);
}
}
// This code has been contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to partition a linked list
// around a given value.
/* Link list Node */
class Node {
constructor(val) {
this.data = val;
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 a new list
// (using the existing nodes) and
// return head of new list.
function partition(head , x) {
/*
* Let us initialize start and tail nodes of new list
*/
var tail = head;
// Now iterate original list and connect nodes
var curr = head;
while (curr != null) {
var next = curr.next;
if (curr.data < x) {
/* Insert node at head. */
curr.next = head;
head = curr;
}
else // Append to the list of greater values
{
/* Insert node at tail. */
tail.next = curr;
tail = curr;
}
curr = next;
}
tail.next = null;
// The head has changed, so we need
// to return it to the user.
return head;
}
/* 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(3);
head.next = newNode(5);
head.next.next = newNode(8);
head.next.next.next = newNode(2);
head.next.next.next.next = newNode(10);
head.next.next.next.next.next = newNode(2);
head.next.next.next.next.next.next = newNode(1);
var x = 5;
head = partition(head, x);
printList(head);
// This code contributed by Rajput-Ji
</script>
Producción
1 2 2 3 5 8 10
Análisis de Complejidad:
- Complejidad temporal: O(n).
- Complejidad espacial: O(1), ya que no estamos usando más de 4 punteros.
Este artículo es una contribución del Sr. Somesh Awasthi . 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 contribuido@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