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 vinculada, necesitamos cambiar el siguiente puntero del k-ésimo Node a NULL, el siguiente puntero del último Node debe apuntar al Node principal anterior y, finalmente, cambiar el encabezado a (k+1)-ésimo 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 \n";
printList(head);
rotate(&head, 4);
cout << "\nRotated Linked list \n";
printList(head);
return (0);
}
// This code is contributed by rathbhupendra
C
// C program to rotate a linked list counter clock wise
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
struct Node {
int data;
struct 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(struct 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.
struct 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
struct 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(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 linked list */
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
/* Driver program to test above function*/
int main(void)
{
/* Start with the empty list */
struct Node* head = NULL;
// create a list 10->20->30->40->50->60
for (int i = 60; i > 0; i -= 10)
push(&head, i);
printf("Given linked list \n");
printList(head);
rotate(&head, 4);
printf("\nRotated Linked list \n");
printList(head);
return (0);
}
Java
// Java program to rotate a linked list
class LinkedList {
Node head; // head of list
/* Linked list Node*/
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
// 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(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;
// 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;
// Change head to (k+1)th node
// head is now changed to node 50
head = kthNode.next;
// change next of kth node to null
kthNode.next = null;
}
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
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;
}
void printList()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
/* Driver program to test above functions */
public static void main(String args[])
{
LinkedList llist = new LinkedList();
// create a list 10->20->30->40->50->60
for (int i = 60; i >= 10; i -= 10)
llist.push(i);
System.out.println("Given list");
llist.printList();
llist.rotate(4);
System.out.println("Rotated Linked List");
llist.printList();
}
} /* This code is contributed by Rajat Mishra */
Python
# Python program to rotate a linked list # Node class class Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None class LinkedList: # Function to initialize head def __init__(self): self.head = None # Function to insert a new node at the beginning def push(self, new_data): # allocate node and put the data new_node = Node(new_data) # Make next of new node as head new_node.next = self.head # move the head to point to the new Node self.head = new_node # Utility function to print it the linked LinkedList def printList(self): temp = self.head while(temp): print temp.data, temp = temp.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 of equal to size def rotate(self, k): if k == 0: return # Let us understand the below code for example k = 4 # and list = 10->20->30->40->50->60 current = self.head # current will either point to kth or NULL after # this loop # current will point to node 40 in the above example count = 1 while(count <k and current is not None): current = current.next count += 1 # If current is None, k is greater than or equal # to count of nodes in linked list. Don't change # the list in this case if current is None: return # current points to kth node. Store it in a variable # kth node points to node 40 in the above example kthNode = current # current will point to last node after this loop # current will point to node 60 in above example while(current.next is not None): current = current.next # Change next of last node to previous head # Next of 60 is now changed to node 10 current.next = self.head # Change head to (k + 1)th node # head is not changed to node 50 self.head = kthNode.next # change next of kth node to NULL # next of 40 is not NULL kthNode.next = None # Driver program to test above function llist = LinkedList() # Create a list 10->20->30->40->50->60 for i in range(60, 0, -10): llist.push(i) print "Given linked list" llist.printList() llist.rotate(4) print "\nRotated Linked list" llist.printList() # This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// C# program to rotate a linked list
using System;
public class LinkedList {
Node head; // head of list
/* Linked list Node*/
public class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
// 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(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;
// 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;
// Change head to (k+1)th node
// head is now changed to node 50
head = kthNode.next;
// change next of kth node to null
kthNode.next = null;
}
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
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;
}
void printList()
{
Node temp = head;
while (temp != null) {
Console.Write(temp.data + " ");
temp = temp.next;
}
Console.WriteLine();
}
/* Driver code */
public static void Main()
{
LinkedList llist = new LinkedList();
// create a list 10->20->30->40->50->60
for (int i = 60; i >= 10; i -= 10)
llist.push(i);
Console.WriteLine("Given list");
llist.printList();
llist.rotate(4);
Console.WriteLine("Rotated Linked List");
llist.printList();
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to rotate a linked list
var head; // head of list
/* Linked list Node */
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
// 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
function rotate(k) {
if (k == 0)
return;
// Let us understand the
// below code for example k = 4
// and list = 10->20->30->40->50->60.
var current = head;
// current will either point to kth
// or NULL after this
// loop. current will point to node
// 40 in the above example
var 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
var 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;
// Change head to (k+1)th node
// head is now changed to node 50
head = kthNode.next;
// change next of kth node to null
kthNode.next = null;
}
/*
* Given a reference (pointer to pointer) to
the head of a list and an int, push
a new node on the front of the list.
*/
function push(new_data) {
/*
1 & 2: Allocate the Node & Put in the data
*/
var 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 printList() {
var temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
document.write("<br/>");
}
/* Driver program to test above functions */
// create a list 10->20->30->40->50->60
for (i = 60; i >= 10; i -= 10)
push(i);
document.write("Given list<br/>");
printList();
rotate(4);
document.write("Rotated Linked List<br/>");
printList();
// This code is contributed by todaysgaurav
</script>
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.
Espacio Auxiliar : O(1)
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 vinculada por k, primero podemos hacer que la lista vinculada sea circular y luego mover k-1 pasos hacia adelante desde el Node principal, haciendo que el (k-1)-ésimo Node esté al lado de 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 \n";
printList(head);
rotate(&head, 4);
cout << "\nRotated Linked list \n";
printList(head);
return (0);
}
// This code is contributed by pkurada
Java
// Java program to rotate
// a linked list counter clock wise
import java.util.*;
class GFG{
/* Link list node */
static class Node {
int data;
Node next;
};
static Node head = null;
// This function rotates a linked list
// counter-clockwise and updates the
// head. The function assumes that k is
// smaller than size of linked list.
static void rotate( 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;
// Traverse till the end.
while (current.next != null)
current = current.next;
current.next = head;
current = head;
// 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 = current.next;
current.next = null;
}
/* UTILITY FUNCTIONS */
/* Function to push a node */
static void push(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;
/* move the head to point to the new node */
head = new_node;
}
/* Function to print linked list */
static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
}
/* Driver code*/
public static void main(String[] args)
{
/* Start with the empty list */
// create a list 10.20.30.40.50.60
for (int i = 60; i > 0; i -= 10)
push( i);
System.out.print("Given linked list \n");
printList(head);
rotate( 4);
System.out.print("\nRotated Linked list \n");
printList(head);
}
}
// This code IS contributed by gauravrajput1
Python3
# Python3 program to rotate
# a linked list counter clock wise
# Link list node
class Node:
def __init__(self):
self.data = 0
self.next = None
# This function rotates a linked list
# counter-clockwise and updates the
# head. The function assumes that k is
# smaller than size of linked list.
def rotate(head_ref, k):
if (k == 0):
return
# Let us understand the below
# code for example k = 4 and
# list = 10.20.30.40.50.60.
current = head_ref
# Traverse till the end.
while (current.next != None):
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 i in range(k - 1):
current = current.next
# Update the head_ref and last
# element pointer to None
head_ref = current.next
current.next = None
return head_ref
# UTILITY FUNCTIONS
# Function to push a node
def push(head_ref, new_data):
# Allocate node
new_node = 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
# Function to print linked list
def printList(node):
while (node != None):
print(node.data, end = ' ')
node = node.next
# Driver code
if __name__=='__main__':
# Start with the empty list
head = None
# Create a list 10.20.30.40.50.60
for i in range(60, 0, -10):
head = push(head, i)
print("Given linked list ")
printList(head)
head = rotate(head, 4)
print("\nRotated Linked list ")
printList(head)
# This code is contributed by rutvik_56
C#
// C# program to rotate
// a linked list counter clock wise
using System;
class GFG{
/* Link list node */
public class Node {
public int data;
public Node next;
};
static Node head = null;
// This function rotates a linked list
// counter-clockwise and updates the
// head. The function assumes that k is
// smaller than size of linked list.
static void rotate( 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;
// Traverse till the end.
while (current.next != null)
current = current.next;
current.next = head;
current = head;
// 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 = current.next;
current.next = null;
}
/* UTILITY FUNCTIONS */
/* Function to push a node */
static void push(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;
/* move the head to point to the new node */
head = new_node;
}
/* Function to print linked list */
static void printList(Node node)
{
while (node != null)
{
Console.Write(node.data + " ");
node = node.next;
}
}
/* Driver code*/
public static void Main(String[] args)
{
/* Start with the empty list */
// create a list 10.20.30.40.50.60
for (int i = 60; i > 0; i -= 10)
push( i);
Console.Write("Given linked list \n");
printList(head);
rotate( 4);
Console.Write("\nRotated Linked list \n");
printList(head);
}
}
// This code contributed by shikhasingrajput
Javascript
<script>
// Javascript program to rotate
// a linked list counter clock wise
/* Link list node */
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
var head = null;
// This function rotates a linked list
// counter-clockwise and updates the
// head. The function assumes that k is
// smaller than size of linked list.
function rotate(k) {
if (k == 0)
return;
// Let us understand the below
// code for example k = 4 and
// list = 10.20.30.40.50.60.
var current = head;
// Traverse till the end.
while (current.next != null)
current = current.next;
current.next = head;
current = head;
// traverse the linked list
// to k-1 position which
// will be last element for rotated array.
for (i = 0; i < k - 1; i++)
current = current.next;
// update the head_ref and last
// element pointer to null
head = current.next;
current.next = null;
}
/* UTILITY FUNCTIONS */
/* Function to push a node */
function push(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;
/* move the head to point to the new node */
head = new_node;
}
/* Function to print linked list */
function printList( node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
/* Driver code */
/* Start with the empty list */
// create a list 10.20.30.40.50.60
for (i = 60; i > 0; i -= 10)
push(i);
document.write("Given linked list <br/>");
printList(head);
rotate(4);
document.write("<br/>Rotated Linked list <br/>");
printList(head);
// This code contributed by aashish1995
</script>
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.
Espacio Auxiliar : O(1)
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