Dada una lista enlazada y una clave en ella, la tarea es mover todas las apariciones de la clave dada al final de la lista enlazada, manteniendo igual el orden de todos los demás elementos.
Ejemplos:
Input : 1 -> 2 -> 2 -> 4 -> 3
key = 2
Output : 1 -> 4 -> 3 -> 2 -> 2
Input : 6 -> 6 -> 7 -> 6 -> 3 -> 10
key = 6
Output : 7 -> 3 -> 10 -> 6 -> 6 -> 6
Una solución simple es encontrar una por una todas las apariciones de una clave dada en la lista enlazada. Para cada ocurrencia encontrada, insértela al final. Lo hacemos hasta que todas las apariciones de la clave dada se muevan al final.
Complejidad temporal: O(n 2 )
Solución eficiente 1: es mantener dos punteros:
pCrawl => Puntero para recorrer toda la lista uno por uno.
pKey => Puntero a una ocurrencia de la clave si se encuentra una clave. De lo contrario, igual que pCrawl.
Comenzamos los dos punteros anteriores desde el encabezado de la lista enlazada. Movemos pKey solo cuando pKey no apunta a una tecla. Siempre movemos pCrawl . Entonces, cuando pCrawl y pKey no son lo mismo, debemos haber encontrado una clave que se encuentra antes de pCrawl , por lo que intercambiamos entre pCrawl y pKey , y movemos pKeya la siguiente ubicación. El ciclo invariable es que, después del intercambio de datos, todos los elementos desde pKey hasta pCrawl son claves.
A continuación se muestra la implementación de este enfoque.
Python3
# Python3 program to move all occurrences of a
# given key to end.
# Linked List node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# A utility function to create a new node.
def newNode(x):
temp = Node(0)
temp.data = x
temp.next = None
return temp
# Utility function to print the elements
# in Linked list
def printList( head):
temp = head
while (temp != None) :
print( temp.data,end = " ")
temp = temp.next
print()
# Moves all occurrences of given key to
# end of linked list.
def moveToEnd(head, key):
# Keeps track of locations where key
# is present.
pKey = head
# Traverse list
pCrawl = head
while (pCrawl != None) :
# If current pointer is not same as pointer
# to a key location, then we must have found
# a key in linked list. We swap data of pCrawl
# and pKey and move pKey to next position.
if (pCrawl != pKey and pCrawl.data != key) :
pKey.data = pCrawl.data
pCrawl.data = key
pKey = pKey.next
# Find next position where key is present
if (pKey.data != key):
pKey = pKey.next
# Moving to next Node
pCrawl = pCrawl.next
return head
# Driver code
head = newNode(10)
head.next = newNode(20)
head.next.next = newNode(10)
head.next.next.next = newNode(30)
head.next.next.next.next = newNode(40)
head.next.next.next.next.next = newNode(10)
head.next.next.next.next.next.next = newNode(60)
print("Before moveToEnd(), the Linked list is
")
printList(head)
key = 10
head = moveToEnd(head, key)
print("
After moveToEnd(), the Linked list is
")
printList(head)
# This code is contributed by Arnab Kundu
Producción:
Before moveToEnd(), the Linked list is 10 20 10 30 40 10 60 After moveToEnd(), the Linked list is 20 30 40 60 10 10 10
Complejidad de tiempo: O (n) requiere solo un recorrido de la lista.
Solución eficiente 2:
1. Recorra la lista enlazada y tome un puntero en la cola.
2. Ahora, busque la clave y el Node->datos. Si son iguales, mueva el Node al último-siguiente, de lo contrario avance.
Python3
# Python3 code to remove key element to
# end of linked list
# A Linked list Node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# A utility function to create a new node.
def newNode(x):
temp = Node(x)
return temp
# Function to remove key to end
def keyToEnd(head, key):
# Node to keep pointing to tail
tail = head
if (head == None):
return None
while (tail.next != None):
tail = tail.next
# Node to point to last of linked list
last = tail
current = head
prev = None
# Node prev2 to point to previous
# when head.data!=key
prev2 = None
# Loop to perform operations to
# remove key to end
while (current != tail):
if (current.data == key and prev2 == None):
prev = current
current = current.next
head = current
last.next = prev
last = last.next
last.next = None
prev = None
else:
if (current.data == key and prev2 != None):
prev = current
current = current.next
prev2.next = current
last.next = prev
last = last.next
last.next = None
elif (current != tail):
prev2 = current
current = current.next
return head
# Function to display linked list
def printList(head):
temp = head
while (temp != None):
print(temp.data, end = ' ')
temp = temp.next
print()
# Driver Code
if __name__=='__main__':
root = newNode(5)
root.next = newNode(2)
root.next.next = newNode(2)
root.next.next.next = newNode(7)
root.next.next.next.next = newNode(2)
root.next.next.next.next.next = newNode(2)
root.next.next.next.next.next.next = newNode(2)
key = 2
print("Linked List before operations :")
printList(root)
print("Linked List after operations :")
root = keyToEnd(root, key)
printList(root)
# This code is contributed by rutvik_56
Producción:
Linked List before operations : 5 2 2 7 2 2 2 Linked List after operations : 5 7 2 2 2 2 2
Gracias a Ravinder Kumar por sugerir este método.
Solución eficiente 3: es mantener una lista separada de claves. Inicializamos esta lista de claves como vacía. Recorremos la lista dada. Por cada clave encontrada, la eliminamos de la lista original y la insertamos en una lista separada de claves. Finalmente vinculamos la lista de claves al final de la lista restante. La complejidad temporal de esta solución también es O(n) y también requiere solo un recorrido de la lista.
Consulte el artículo completo sobre Mover todas las apariciones de un elemento para terminar en una lista vinculada 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