给定一个单链表，将链表逆时针旋转 k 个节点。其中 k 是给定的正整数。例如，如果给定的链表是 10->20->30->40->50->60 且 k 为 4，则该链表应修改为 50->60->10->20->30- > 40。假设 k 小于链表中的节点数。
方法一：
要旋转链表，我们需要将第k个节点的next改为NULL，将最后一个节点的next改为上一个头节点，最后将head改为第(k+1)个节点。所以我们需要掌握三个节点：第k个节点、第(k+1)个节点和最后一个节点。
从头开始遍历列表并在第 k 个节点处停止。存储指向第 k 个节点的指针。我们可以使用 kthNode->next 得到第 (k+1) 个节点。继续遍历直到最后并存储指向最后一个节点的指针。最后，如上所述更改指针。
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; void rotate(Node** head_ref, int k) { if (k == 0) return; Node* current = *head_ref; int count = 1; while (count < k && current != NULL) { current = current->next; count++; } if (current == NULL) return; Node* kthNode = current; while (current->next != NULL) current = current->next; current->next = *head_ref; *head_ref = kthNode->next; kthNode->next = NULL; } void push(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void printList(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } int main(void) { Node* head = NULL; 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); }
输出：
Given linked list 10 20 30 40 50 60 Rotated Linked list 50 60 10 20 30 40
时间复杂度：O(n)，其中 n 是链表中的节点数。代码只遍历链表一次。
如果您发现任何不正确的内容，或者您想分享有关上述主题的更多信息，请发表评论。
方法2：
将链表旋转k，我们可以先使链表循环，然后从头节点向前移动k-1步，使第（k-1）个节点紧挨着空，并以第k个节点为头。
#include <bits/stdc++.h> using namespace std; 、 class Node { public: int data; Node* next; }; void rotate(Node** head_ref, int k) { if (k == 0) return; Node* current = *head_ref; while (current->next != NULL) current = current->next; current->next = *head_ref; current = *head_ref; for (int i = 0; i < k - 1; i++) current = current->next; *head_ref = current->next; current->next = NULL; } void push(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void printList(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } int main(void) { Node* head = NULL; 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); }
输出：
Given linked list 10 20 30 40 50 60 Rotated Linked list 50 60 10 20 30 40
