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<stdio.h>
#include<stdlib.h>
// A linked list node
struct Node
{
int data;
struct Node *next;
};
/* We are using a double pointer head_ref
here because we change head of the
linked list inside this function.*/
void moveToFront(struct 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 */
struct Node *secLast = NULL;
struct 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(struct Node** head_ref,
int new_data)
{
// Allocate node
struct Node* new_node =
(struct Node*) malloc(sizeof(struct 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(struct Node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
// Driver code
int main()
{
struct 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);
printf("Linked list before moving last to front");
printList(start);
moveToFront(&start);
printf("Linked list after removing last to front");
printList(start);
return 0;
}
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