Dada una lista enlazada individualmente, gire la lista enlazada en sentido contrario a las agujas del reloj por k Nodes. Donde k es un entero positivo dado. Por ejemplo, si la lista enlazada dada es 10->20->30->40->50->60 y k es 4, la lista debe modificarse a 50->60->10->20->30- >40. Suponga que k es menor que el número de Nodes en una lista enlazada.
Método 1:
para rotar la lista enlazada, necesitamos cambiar el siguiente Node k-ésimo a NULL, el siguiente del último Node al Node principal anterior y, finalmente, cambiar el Node principal a (k+1) Node. Así que necesitamos conseguir tres Nodes: k-ésimo Node, (k+1)-ésimo Node y último Node.
Recorra la lista desde el principio y deténgase en el k-ésimo Node. Almacene el puntero al k-ésimo Node. Podemos obtener (k+1) Node usando kthNode->next. Continúe recorriendo hasta el final y almacene un puntero al último Node también. Finalmente, cambie los punteros como se indicó anteriormente.
La imagen a continuación muestra cómo funciona la función de rotación en el código:
C++
// C++ program to rotate a
// linked list counter clock wise
#include <bits/stdc++.h>
using namespace std;
// Link list node
class Node
{
public:
int data;
Node* next;
};
// This function rotates a linked list
// counter-clockwise and updates the
// head. The function assumes that k is
// smaller than size of linked list.
// It doesn't modify the list if
// k is greater than or equal to size
void rotate(Node** head_ref, int k)
{
if (k == 0)
return;
// Let us understand the below
// code for example k = 4 and
// list = 10->20->30->40->50->60.
Node* current = *head_ref;
// current will either point to
// kth or NULL after this loop.
// current will point to node
// 40 in the above example
int count = 1;
while (count < k &&
current != NULL)
{
current = current->next;
count++;
}
// If current is NULL, k is greater
// than or equal to count of nodes
// in linked list. Don't change the
// list in this case
if (current == NULL)
return;
// current points to kth node.
// Store it in a variable. kthNode
// points to node 40 in the above
// example
Node* kthNode = current;
// current will point to
// last node after this loop
// current will point to
// node 60 in the above example
while (current->next != NULL)
current = current->next;
// Change next of last node to
// previous head. Next of 60 is
// now changed to node 10
current->next = *head_ref;
// Change head to (k+1)th node
// head is now changed to node 50
*head_ref = kthNode->next;
// Change next of kth node to NULL
// next of 40 is now NULL
kthNode->next = NULL;
}
// UTILITY FUNCTIONS
// Function to push a node
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 linked list
void printList(Node* node)
{
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}
// Driver code
int main(void)
{
// Start with the empty list
Node* head = NULL;
// Create a list
// 10->20->30->40->50->60
for (int i = 60; i > 0; i -= 10)
push(&head, i);
cout << "Given linked list ";
printList(head);
rotate(&head, 4);
cout << "Rotated Linked list ";
printList(head);
return (0);
}
// This code is contributed by rathbhupendra
Producción:
Given linked list 10 20 30 40 50 60 Rotated Linked list 50 60 10 20 30 40
Complejidad de tiempo: O(n) donde n es el número de Nodes en la lista enlazada. El código atraviesa la lista enlazada solo una vez.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Método 2:
para rotar una lista enlazada por k, primero podemos hacer que la lista enlazada sea circular y luego mover k-1 pasos hacia adelante desde el Node principal, haciendo que el (k-1)-ésimo Node esté junto a nulo y hacer que el k-ésimo Node sea la cabeza.
C++
// C++ program to rotate a
// linked list counter clock wise
#include <bits/stdc++.h>
using namespace std;
// Link list node
class Node
{
public:
int data;
Node* next;
};
// This function rotates a linked list
// counter-clockwise and updates the
// head. The function assumes that k is
// smaller than size of linked list.
void rotate(Node** head_ref, int k)
{
if (k == 0)
return;
// Let us understand the below
// code for example k = 4 and
// list = 10->20->30->40->50->60.
Node* current = *head_ref;
// Traverse till the end.
while (current->next != NULL)
current = current->next;
current->next = *head_ref;
current = *head_ref;
// Traverse the linked list to
// k-1 position which will be
// last element for rotated array.
for (int i = 0; i < k - 1; i++)
current = current->next;
// Update the head_ref and last
// element pointer to NULL
*head_ref = current->next;
current->next = NULL;
}
// UTILITY FUNCTIONS
// Function to push a node
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 linked list
void printList(Node* node)
{
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}
// Driver code
int main(void)
{
// Start with the empty list
Node* head = NULL;
// Create a list
// 10->20->30->40->50->60
for (int i = 60; i > 0; i -= 10)
push(&head, i);
cout << "Given linked list ";
printList(head);
rotate(&head, 4);
cout << "Rotated Linked list ";
printList(head);
return (0);
}
// This code is contributed by pkurada
Producción:
Given linked list 10 20 30 40 50 60 Rotated Linked list 50 60 10 20 30 40
Consulte el artículo completo sobre Rotar 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