Escriba una función que mueva el último elemento al frente en una lista enlazada simple dada. Por ejemplo, si la lista enlazada dada es 1->2->3->4->5, entonces la función debería cambiar la lista a 5->1->2->3->4.
Algoritmo:
recorrer la lista hasta el último Node. Utilice dos punteros: uno para almacenar la dirección del último Node y el otro para la dirección del penúltimo Node. Después del final del ciclo, realice las siguientes operaciones.
- Hacer penúltimo como último (secLast->next = NULL).
- Establecer el penúltimo como encabezado (last->next = *head_ref).
- Hacer último como cabeza (*head_ref = último).
Java
/* Java Program to move last element to
front in a given linked list */
class LinkedList
{
// Head of list
Node head;
// Linked list Node
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void moveToFront()
{
/* If linked list is empty or
it contains only one node
then simply return. */
if(head == null ||
head.next == null)
return;
/* Initialize second last and
last pointers */
Node secLast = null;
Node last = head;
/* After this loop secLast contains
address of second last node and
last contains address of last node
in Linked List */
while (last.next != null)
{
secLast = last;
last = last.next;
}
// Set the next of second last as null
secLast.next = null;
// Set the next of last as head
last.next = head;
// Change head to point to
// last node.
head = last;
}
// Utility functions
/* Inserts a new Node at front
of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
// 3. Make next of new Node as head
new_node.next = head;
// 4. Move the head to point to
// new Node
head = new_node;
}
// Function to print linked list
void printList()
{
Node temp = head;
while(temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
// Driver code
public static void main(String args[])
{
LinkedList llist = new LinkedList();
/* Constructed Linked List is
1->2->3->4->5->null */
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);
System.out.println(
"Linked List before moving last to front ");
llist.printList();
llist.moveToFront();
System.out.println(
"Linked List after moving last to front ");
llist.printList();
}
}
// This code is contributed by Rajat Mishra
Producción:
Linked list before moving last to front 1 2 3 4 5 Linked list after removing last to front 5 1 2 3 4
Complejidad de tiempo: O(n) donde n es el número de Nodes en la lista enlazada dada.
Consulte el artículo completo sobre Mover el último elemento al frente de una lista vinculada determinada 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