Dada una lista enlazada que se ordena en función de valores absolutos. Ordene la lista según los valores reales.
Ejemplos:
Input: 1 -> -10 Output: -10 -> 1 Input: 1 -> -2 -> -3 -> 4 -> -5 Output: -5 -> -3 -> -2 -> 1 -> 4 Input: -5 -> -10 Output: -10 -> -5 Input: 5 -> 10 Output: 5 -> 10
Fuente: entrevista de Amazon
Una solución simple es recorrer la lista enlazada de principio a fin. Para cada Node visitado, verifique si está fuera de servicio. Si es así, retírelo de su posición actual e insértelo en la posición correcta. Esta es la implementación del ordenamiento por inserción para la lista enlazada y la complejidad temporal de esta solución es O(n*n).
Una mejor solución es ordenar la lista enlazada usando merge sort . La complejidad temporal de esta solución es O(n Log n).
Una solución eficiente puede funcionar en tiempo O(n). Una observación importante es que todos los elementos negativos están presentes en orden inverso. Entonces recorremos la lista, cada vez que encontramos un elemento que está fuera de servicio, lo movemos al frente de la lista enlazada.
A continuación se muestra la implementación de la idea anterior.
cada vez que encontramos un elemento que está fuera de servicio, lo movemos al frente de la lista enlazada.
A continuación se muestra la implementación de la idea anterior.
Python3
# Python3 program to sort a linked list,
# already sorted by absolute values
# Linked list Node
class Node:
def __init__(self, d):
self.data = d
self.next = None
class SortList:
def __init__(self):
self.head = None
# To sort a linked list by actual values.
# The list is assumed to be sorted by
# absolute values.
def sortedList(self, head):
# Initialize previous and
# current nodes
prev = self.head
curr = self.head.next
# Traverse list
while(curr != None):
# If curr is smaller than prev,
# then it must be moved to head
if(curr.data < prev.data):
# Detach curr from linked list
prev.next = curr.next
# Move current node to beginning
curr.next = self.head
self.head = curr
# Update current
curr = prev
# Nothing to do if current element
# is at right place
else:
prev = curr
# Move current
curr = curr.next
return self.head
# Inserts a new Node at front of
# the list
def push(self, new_data):
# 1 & 2: Allocate the Node &
# Put in the data
new_node = Node(new_data)
# 3. Make next of new Node as head
new_node.next = self.head
# 4. Move the head to point to
# new Node
self.head = new_node
# Function to print linked list
def printList(self, head):
temp = head
while (temp != None):
print(temp.data, end = " ")
temp = temp.next
print()
# Driver Code
llist = SortList()
# Constructed Linked List is
# 1->2->3->4->5->6->7->8->8->9->null
llist.push(-5)
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(-2)
llist.push(1)
llist.push(0)
print("Original List :")
llist.printList(llist.head)
start = llist.sortedList(llist.head)
print("Sorted list :")
llist.printList(start)
# This code is contributed by Prerna Saini
Producción:
Original list : 0 -> 1 -> -2 -> 3 -> 4 -> 5 -> -5 Sorted list : -5 -> -2 -> 0 -> 1 -> 3 -> 4 -> 5
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
¡ Consulte el artículo completo sobre Ordenar lista enlazada que ya está ordenada en valores absolutos 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