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.
Javascript
<script>
// Javascript program to move all occurrences of a
// given key to end.
// A Linked list Node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// A utility function to create a new node.
function newNode(x) {
var temp = new Node();
temp.data = x;
temp.next = null;
return temp;
}
// Utility function to print the elements
// in Linked list
function printList(head) {
var temp = head;
while (temp != null) {
document.write( temp.data+" ");
temp = temp.next;
}
document.write("<br/>");
}
// Moves all occurrences of given key to
// end of linked list.
function moveToEnd(head , key) {
// Keeps track of locations where key
// is present.
var pKey = head;
// Traverse list
var pCrawl = head;
while (pCrawl != null) {
// 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 && 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;
}
}
// Driver code
var 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);
document.write(
"Before moveToEnd(), the Linked list is<br/>"
);
printList(head);
var key = 10;
moveToEnd(head, key);
document.write(
"<br/>After moveToEnd(), the Linked list is<br/>"
);
printList(head);
// This code contributed by umadevi9616
</script>
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.
Javascript
<script>
// javascript code to remove key element to end of linked list// Node class
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
var root;
// Function to remove key to end
function keyToEnd(head , key) {
// Node to keep pointing to tail
var tail = head;
if (head == null) {
return null;
}
while (tail.next != null) {
tail = tail.next;
}
// Node to point to last of linked list
var last = tail;
var current = head;
var prev = null;
// Node prev2 to point to previous when head.data!=key
var prev2 = null;
// loop to perform operations to remove key to end
while (current != tail) {
if (current.data == key && prev2 == null) {
prev = current;
current = current.next;
head = current;
last.next = prev;
last = last.next;
last.next = null;
prev = null;
} else {
if (current.data == key && prev2 != null) {
prev = current;
current = current.next;
prev2.next = current;
last.next = prev;
last = last.next;
last.next = null;
} else if (current != tail) {
prev2 = current;
current = current.next;
}
}
}
return head;
}
// Function to display linked list
function display(root) {
while (root != null) {
document.write(root.data + " ");
root = root.next;
}
}
// Driver Code
root = new Node(5);
root.next = new Node(2);
root.next.next = new Node(2);
root.next.next.next = new Node(7);
root.next.next.next.next = new Node(2);
root.next.next.next.next.next = new Node(2);
root.next.next.next.next.next.next = new Node(2);
var key = 2;
document.write("Linked List before operations :<br/>");
display(root);
document.write("<br/>Linked List after operations :<br/>");
root = keyToEnd(root, key);
display(root);
// This code contributed by aashish1995
</script>
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