Dada una lista enlazada individualmente y un número entero K , la tarea es rotar la lista enlazada en el sentido de las agujas del reloj hacia la derecha K lugares.
Ejemplos:
Entrada: 1 -> 2 -> 3 -> 4 -> 5 -> NULL, K = 2
Salida: 4 -> 5 -> 1 -> 2 -> 3 -> NULL
Entrada: 7 -> 9 -> 11 – > 13 -> 3 -> 5 -> NULO, K = 12
Salida: 7 -> 9 -> 11 -> 13 -> 3 -> 5 -> NULO
Enfoque: para rotar la lista enlazada, primero verifique si el k dado es mayor que el recuento de Nodes en la lista enlazada o no. Recorra la lista y encuentre la longitud de la lista enlazada, luego compárela con k, si es menor, continúe, de lo contrario, dedúzcala en el rango del tamaño de la lista enlazada tomando el módulo con la longitud de la lista.
Después de eso, reste el valor de k de la longitud de la lista. Ahora, la pregunta se ha cambiado a la rotación izquierda de la lista enlazada, así que siga ese procedimiento:
- Cambie el siguiente del k-ésimo Node a NULL.
- Cambia el siguiente del último Node al Node principal anterior.
- Cambie la cabeza a (k+1)th Node.
Para hacerlo, se requieren los punteros al k-ésimo Node, (k+1)-ésimo Node y al último Node.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
class Node {
public:
int data;
Node* next;
};
/* A utility 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;
}
/* A utility function to print linked list */
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " -> ";
node = node->next;
}
cout << "NULL";
}
// Function that rotates the given linked list
// clockwise by k and returns the updated
// head pointer
Node* rightRotate(Node* head, int k)
{
// If the linked list is empty
if (!head)
return head;
// len is used to store length of the linked list
// tmp will point to the last node after this loop
Node* tmp = head;
int len = 1;
while (tmp->next != NULL) {
tmp = tmp->next;
len++;
}
// If k is greater than the size
// of the linked list
if (k > len)
k = k % len;
// Subtract from length to convert
// it into left rotation
k = len - k;
// If no rotation needed then
// return the head node
if (k == 0 || k == len)
return head;
// current will either point to
// kth or NULL after this loop
Node* current = head;
int cnt = 1;
while (cnt < k && current != NULL) {
current = current->next;
cnt++;
}
// If current is NULL then k is equal to the
// count of nodes in the list
// Don't change the list in this case
if (current == NULL)
return head;
// current points to the kth node
Node* kthnode = current;
// Change next of last node to previous head
tmp->next = head;
// Change head to (k+1)th node
head = kthnode->next;
// Change next of kth node to NULL
kthnode->next = NULL;
// Return the updated head pointer
return head;
}
// Driver code
int main()
{
/* The constructed linked list is:
1->2->3->4->5 */
Node* head = NULL;
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
int k = 2;
// Rotate the linked list
Node* updated_head = rightRotate(head, k);
// Print the rotated linked list
printList(updated_head);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
/* Link list node */
static class Node
{
int data;
Node next;
}
/* A utility function to push a node */
static Node 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;
return head_ref;
}
/* A utility function to print linked list */
static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data + " -> ");
node = node.next;
}
System.out.print( "null");
}
// Function that rotates the given linked list
// clockwise by k and returns the updated
// head pointer
static Node rightRotate(Node head, int k)
{
// If the linked list is empty
if (head == null)
return head;
// len is used to store length of the linked list
// tmp will point to the last node after this loop
Node tmp = head;
int len = 1;
while (tmp.next != null)
{
tmp = tmp.next;
len++;
}
// If k is greater than the size
// of the linked list
if (k > len)
k = k % len;
// Subtract from length to convert
// it into left rotation
k = len - k;
// If no rotation needed then
// return the head node
if (k == 0 || k == len)
return head;
// current will either point to
// kth or null after this loop
Node current = head;
int cnt = 1;
while (cnt < k && current != null)
{
current = current.next;
cnt++;
}
// If current is null then k is equal to the
// count of nodes in the list
// Don't change the list in this case
if (current == null)
return head;
// current points to the kth node
Node kthnode = current;
// Change next of last node to previous head
tmp.next = head;
// Change head to (k+1)th node
head = kthnode.next;
// Change next of kth node to null
kthnode.next = null;
// Return the updated head pointer
return head;
}
// Driver code
public static void main(String args[])
{
/* The constructed linked list is:
1.2.3.4.5 */
Node head = null;
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
int k = 2;
// Rotate the linked list
Node updated_head = rightRotate(head, k);
// Print the rotated linked list
printList(updated_head);
}
}
// This code is contributed by Arnub Kundu
Python3
# Python3 implementation of the approach
''' Link list node '''
class Node:
def __init__(self, data):
self.data = data
self.next = None
''' A utility function to push a node '''
def push(head_ref, new_data):
''' allocate node '''
new_node = Node(new_data)
''' 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
return head_ref
''' A utility function to print linked list '''
def printList(node):
while (node != None):
print(node.data, end=' -> ')
node = node.next
print("NULL")
# Function that rotates the given linked list
# clockwise by k and returns the updated
# head pointer
def rightRotate(head, k):
# If the linked list is empty
if (not head):
return head
# len is used to store length of the linked list
# tmp will point to the last node after this loop
tmp = head
len = 1
while (tmp.next != None):
tmp = tmp.next
len += 1
# If k is greater than the size
# of the linked list
if (k > len):
k = k % len
# Subtract from length to convert
# it into left rotation
k = len - k
# If no rotation needed then
# return the head node
if (k == 0 or k == len):
return head
# current will either point to
# kth or None after this loop
current = head
cnt = 1
while (cnt < k and current != None):
current = current.next
cnt += 1
# If current is None then k is equal to the
# count of nodes in the list
# Don't change the list in this case
if (current == None):
return head
# current points to the kth node
kthnode = current
# Change next of last node to previous head
tmp.next = head
# Change head to (k+1)th node
head = kthnode.next
# Change next of kth node to None
kthnode.next = None
# Return the updated head pointer
return head
# Driver code
if __name__ == '__main__':
''' The constructed linked list is:
1.2.3.4.5 '''
head = None
head = push(head, 5)
head = push(head, 4)
head = push(head, 3)
head = push(head, 2)
head = push(head, 1)
k = 2
# Rotate the linked list
updated_head = rightRotate(head, k)
# Print the rotated linked list
printList(updated_head)
# This code is contributed by rutvik_56
C#
// C# implementation of the approach
using System;
class GFG
{
/* Link list node */
public class Node
{
public int data;
public Node next;
}
/* A utility function to push a node */
static Node 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;
return head_ref;
}
/* A utility function to print linked list */
static void printList(Node node)
{
while (node != null)
{
Console.Write(node.data + " -> ");
node = node.next;
}
Console.Write("null");
}
// Function that rotates the given linked list
// clockwise by k and returns the updated
// head pointer
static Node rightRotate(Node head, int k)
{
// If the linked list is empty
if (head == null)
return head;
// len is used to store length of
// the linked list, tmp will point
// to the last node after this loop
Node tmp = head;
int len = 1;
while (tmp.next != null)
{
tmp = tmp.next;
len++;
}
// If k is greater than the size
// of the linked list
if (k > len)
k = k % len;
// Subtract from length to convert
// it into left rotation
k = len - k;
// If no rotation needed then
// return the head node
if (k == 0 || k == len)
return head;
// current will either point to
// kth or null after this loop
Node current = head;
int cnt = 1;
while (cnt < k && current != null)
{
current = current.next;
cnt++;
}
// If current is null then k is equal
// to the count of nodes in the list
// Don't change the list in this case
if (current == null)
return head;
// current points to the kth node
Node kthnode = current;
// Change next of last node
// to previous head
tmp.next = head;
// Change head to (k+1)th node
head = kthnode.next;
// Change next of kth node to null
kthnode.next = null;
// Return the updated head pointer
return head;
}
// Driver code
public static void Main(String []args)
{
/* The constructed linked list is:
1.2.3.4.5 */
Node head = null;
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
int k = 2;
// Rotate the linked list
Node updated_head = rightRotate(head, k);
// Print the rotated linked list
printList(updated_head);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation of the approach
/* Link list node */
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
/* A utility function to push a node */
function push(head_ref , new_data) {
/* allocate node */
var 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;
return head_ref;
}
/* A utility function to print linked list */
function printList(node) {
while (node != null) {
document.write(node.data + " -> ");
node = node.next;
}
document.write("null");
}
// Function that rotates the given linked list
// clockwise by k and returns the updated
// head pointer
function rightRotate(head , k) {
// If the linked list is empty
if (head == null)
return head;
// len is used to store length
// of the linked list
// tmp will point to the last
// node after this loop
var tmp = head;
var len = 1;
while (tmp.next != null) {
tmp = tmp.next;
len++;
}
// If k is greater than the size
// of the linked list
if (k > len)
k = k % len;
// Subtract from length to convert
// it into left rotation
k = len - k;
// If no rotation needed then
// return the head node
if (k == 0 || k == len)
return head;
// current will either point to
// kth or null after this loop
var current = head;
var cnt = 1;
while (cnt < k && current != null) {
current = current.next;
cnt++;
}
// If current is null then k is equal to the
// count of nodes in the list
// Don't change the list in this case
if (current == null)
return head;
// current points to the kth node
var kthnode = current;
// Change next of last node to previous head
tmp.next = head;
// Change head to (k+1)th node
head = kthnode.next;
// Change next of kth node to null
kthnode.next = null;
// Return the updated head pointer
return head;
}
// Driver code
/*
* The constructed linked list is: 1.2.3.4.5
*/
var head = null;
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
var k = 2;
// Rotate the linked list
var updated_head = rightRotate(head, k);
// Print the rotated linked list
printList(updated_head);
// This code contributed by Rajput-Ji
</script>
Producción:
4 -> 5 -> 1 -> 2 -> 3 -> NULL
Complejidad de tiempo: O(n) donde n es el número de Nodes en la lista enlazada.
Espacio Auxiliar: O(1)
Enfoque basado en STL:
Este problema también se puede resolver utilizando la estructura de datos deque proporcionada en C++ STL
Acercarse :
Inicialice un deque con el tipo Node* y empuje la lista enlazada dentro de él. Luego siga apareciendo desde atrás y agregando ese Node al frente hasta que el número de operaciones no sea igual a k.
C++
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
Node* next;
Node(int d)
{
val = d;
next = NULL;
}
};
void build(Node*& head, int val)
{
if (head == NULL) {
head = new Node(val);
}
else {
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = new Node(val);
}
}
Node* rotate_clockwise(Node* head, int k)
{
if (head == NULL) {
return NULL;
}
deque<Node*> q;
Node* temp = head;
while (temp != NULL) {
q.push_back(temp);
temp = temp->next;
}
k %= q.size();
while (
k--) // popping from back and adding to it's front
{
q.back()->next = q.front();
q.push_front(q.back());
q.pop_back();
q.back()->next = NULL;
}
return q.front();
}
void print(Node* head)
{
while (head != NULL) {
cout << head->val << " -> ";
head = head->next;
}
cout << "NULL";
cout << endl;
}
int main()
{
Node* head = NULL;
build(head, 1);
build(head, 2);
build(head, 3);
build(head, 4);
build(head, 5);
int k = 2;
Node* r = rotate_clockwise(head, k);
print(r);
return 0;
}
Producción
4 -> 5 -> 1 -> 2 -> 3 -> NULL
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por pratyushranjan14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA