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.
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 elif (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.
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