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.
Java
// Java program to move all occurrences of a
// given key to end.
class GFG {
// A Linked list Node
static class Node {
int data;
Node next;
}
// A utility function to create a new node.
static Node newNode(int x)
{
Node temp = new Node();
temp.data = x;
temp.next = null;
return temp;
}
// Utility function to print the elements
// in Linked list
static void printList(Node head)
{
Node temp = head;
while (temp != null) {
System.out.printf("%d ", temp.data);
temp = temp.next;
}
System.out.printf("
");
}
// Moves all occurrences of given key to
// end of linked list.
static void moveToEnd(Node head, int key)
{
// Keeps track of locations where key
// is present.
Node pKey = head;
// Traverse list
Node 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
public static void main(String args[])
{
Node 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);
System.out.printf("Before moveToEnd(), the Linked list is
");
printList(head);
int key = 10;
moveToEnd(head, key);
System.out.printf("
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.
Espacio Auxiliar: O(1)
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.
Java
// Java code to remove key element to end of linked list
import java.util.*;
// Node class
class Node {
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
class gfg {
static Node root;
// Function to remove key to end
public static Node keyToEnd(Node head, int key)
{
// Node to keep pointing to tail
Node tail = head;
if (head == null) {
return null;
}
while (tail.next != null) {
tail = tail.next;
}
// Node to point to last of linked list
Node last = tail;
Node current = head;
Node prev = null;
// Node prev2 to point to previous when head.data!=key
Node 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
public static void display(Node root)
{
while (root != null) {
System.out.print(root.data + " ");
root = root.next;
}
}
// Driver Code
public static void main(String args[])
{
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);
int key = 2;
System.out.println("Linked List before operations :");
display(root);
System.out.println("
Linked List after operations :");
root = keyToEnd(root, key);
display(root);
}
}
Producción:
Linked List before operations : 5 2 2 7 2 2 2 Linked List after operations : 5 7 2 2 2 2 2
Complejidad de tiempo: O(n), donde n representa el tamaño de la lista dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
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