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).
C++
/* C++ Program to move last element
to front in a given linked list */
#include <bits/stdc++.h>
using namespace std;
// A linked list node
class Node
{
public:
int data;
Node *next;
};
/* We are using a double pointer
head_ref here because we change
head of the linked list inside
this function.*/
void moveToFront(Node **head_ref)
{
/* If linked list is empty, or
it contains only one node,
then nothing needs to be done,
simply return */
if (*head_ref == NULL ||
(*head_ref)->next == NULL)
return;
/* Initialize second last
and last pointers */
Node *secLast = NULL;
Node *last = *head_ref;
/* 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 next of last as head node
last->next = *head_ref;
/* Change the head pointer
to point to last node now */
*head_ref = last;
}
// UTILITY FUNCTIONS
/* Function to add a node
at the beginning of Linked List */
void push(Node** head_ref,
int new_data)
{
// Allocate node
Node* new_node = new Node();
// Put in the data
new_node->data = new_data;
// Link the old list off the
// new node
new_node->next = (*head_ref);
// Move the head to point to the
// new node
(*head_ref) = new_node;
}
/* Function to print nodes in a
given linked list */
void printList(Node *node)
{
while(node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}
// Driver code
int main()
{
Node *start = NULL;
/* The constructed linked list is:
1->2->3->4->5 */
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);
cout <<
"Linked list before moving last to front";
printList(start);
moveToFront(&start);
cout <<
"Linked list after removing last to front";
printList(start);
return 0;
}
// This code is contributed by rathbhupendra
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