Dada una lista enlazada de 0, 1 y 2, ordénela.
Ejemplos:
Input: 2->1->2->1->1->2->0->1->0 Output: 0->0->1->1->1->1->2->2->2 The sorted Array is 0, 0, 1, 1, 1, 1, 2, 2, 2. Input: 2->1->0 Output: 0->1->2 The sorted Array is 0, 1, 2
Método 1: hay una solución discutida en la publicación a continuación que funciona cambiando los datos de los Nodes.
Ordenar una lista enlazada de 0, 1 y 2
La solución anterior no funciona cuando estos valores tienen datos asociados con ellos.
Por ejemplo, estos tres representan tres colores y diferentes tipos de objetos asociados con los colores y clasifican los objetos (conectados con una lista vinculada) en función de los colores.
Método 2: en esta publicación, se analiza una nueva solución que funciona cambiando los enlaces.
Enfoque: Iterar a través de la lista enlazada. Mantenga 3 punteros llamados cero, uno y dos para apuntar a los Nodes finales actuales de las listas vinculadas que contienen 0, 1 y 2 respectivamente. Para cada Node recorrido, lo adjuntamos al final de su lista correspondiente. Finalmente, vinculamos las tres listas. Para evitar muchas verificaciones nulas, usamos tres punteros ficticios zeroD, oneD y twoD que funcionan como encabezados ficticios de tres listas.
Python3
# Python3 Program to sort a linked list
# 0s, 1s or 2s by changing links
import math
# Link list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
#Node* newNode( data)
# Sort a linked list of 0s, 1s
# and 2s by changing pointers.
def sortList(head):
if (head == None or
head.next == None):
return head
# Create three dummy nodes to point
# to beginning of three linked lists.
# These dummy nodes are created to
# avoid many None checks.
zeroD = Node(0)
oneD = Node(0)
twoD = Node(0)
# Initialize current pointers for
# three lists and whole list.
zero = zeroD
one = oneD
two = twoD
# Traverse list
curr = head
while (curr):
if (curr.data == 0):
zero.next = curr
zero = zero.next
curr = curr.next
elif(curr.data == 1):
one.next = curr
one = one.next
curr = curr.next
else:
two.next = curr
two = two.next
curr = curr.next
# Attach three lists
zero.next = (oneD.next) if (oneD.next)
else (twoD.next)
one.next = twoD.next
two.next = None
# Updated head
head = zeroD.next
# Delete dummy nodes
return head
# Function to create and return
# a node
def newNode(data):
# Allocating space
newNode = Node(data)
# Inserting the required data
newNode.data = data
newNode.next = None
return newNode
# Function to print linked list
def prList(node):
while (node != None):
print(node.data, end = " ")
node = node.next
# Driver Code
if __name__=='__main__':
# Creating the list 1.2.4.5
head = newNode(1)
head.next = newNode(2)
head.next.next = newNode(0)
head.next.next.next = newNode(1)
print("Linked List Before Sorting")
prList(head)
head = sortList(head)
print("Linked List After Sorting")
prList(head)
# This code is contributed by Srathore
Producción :
Linked List Before Sorting 1 2 0 1 Linked List After Sorting 0 1 1 2
Análisis de Complejidad:
- Complejidad de tiempo: O(n) donde n es un número de Nodes en la lista enlazada.
Solo se necesita un recorrido de la lista enlazada. - Espacio Auxiliar: O(1).
Como no se requiere espacio adicional.
Consulte el artículo completo sobre Ordenar una lista enlazada de 0, 1 y 2 cambiando los enlaces 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