给定一个单链表，将链表逆时针旋转k个节点。其中k是给定的正整数。例如，如果给定的链表是10->20->30->40->50->60，且k为4，则该列表应修改为50->60->10->20->30->40。假设k小于链表中的节点数。
null
方法1： 要旋转链表，我们需要将第k个节点的下一个节点更改为NULL，将最后一个节点的下一个节点更改为前一个头节点，最后将头更改为（k+1）个节点。所以我们需要得到三个节点：第k个节点，（k+1）个节点，和最后一个节点。 从开始遍历列表，并在第k个节点处停止。存储指向第k个节点的指针。我们可以使用kthNode->next获得第（k+1）个节点。继续遍历直到结束，并存储指向最后一个节点的指针。最后，如上所述更改指针。
下图显示了如何在代码中旋转函数：
![图片[1]-旋转链表-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/cdn-uploads/20190621144237/Rotate-a-Linked-List.png)
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 |
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 " ); printList(head); rotate(&head, 4); printf ( "Rotated Linked list " ); 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 "Rotated 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> |
输出：
Given linked list10 20 30 40 50 60Rotated Linked list50 60 10 20 30 40
时间复杂度：O（n），其中n是链表中的节点数。代码只遍历链接列表一次。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
方法2： 要按k旋转链表，我们可以先使链表循环，然后从头节点向前移动k-1步，使第（k-1）个节点的下一个节点为空，并使第k个节点为头节点。
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 |
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 " ); printList(head); rotate( 4 ); System.out.print( "Rotated Linked list " ); 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 ( "Rotated 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 " ); printList(head); rotate( 4); Console.Write( "Rotated Linked list " ); 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> |
输出：
Given linked list 10 20 30 40 50 60 Rotated Linked list 50 60 10 20 30 40
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
