C++ 程序 将链表中从位置 M 到位置 N 的子列表向右旋转 K 次
给定一个链表和两个位置 ‘m’ 和 ‘n’。任务是将位置 m 到 n 的子列表向右旋转 k 次。
示例:
输入: list = 1->2->3->4->5->6, m = 2, n = 5, k = 2
输出: 1->4->5->2->3->6 将子列表 2 3 4 5 向右旋转 2 次,然后修改后的列表为:1 4 5 2 3 6
输入: list = 20->45->32->34->22->28, m = 3, n = 6, k = 3
输出: 20->45->34->22->28->32 将子列表 32 34 22 28 向右旋转 3 次,然后修改后的列表为:20 45 34 22 28 32
方法: 要将给定的子列表从 m 到 n 的元素向右旋转,将列表从 (n-k+1) th 到 n th 节点移动到子列表的开始处以结束旋转。如果 k 大于子列表的大小,则将其对子列表的大小取模。因此,通过指针和计数器遍历列表,并保存 (m-1) th 节点,稍后使其指向 (n-k+1) th 节点,并将 (n-k+1) th 节点带到子列表的开始(前面)。类似地,我们将保存 m th 节点,稍后使 n th 节点指向它。为了保持其余列表不变,我们将使 (n-k) th 节点指向 n 的下一个节点(可能为空)。最后,我们将得到 k 次右旋转的子列表。下面是上述方法的实现:
// 上述方法的C ++实现
#include <bits/stdc++.h>
using namespace std;
// 链表中节点的定义
struct ListNode {
int data;
struct ListNode* next;
};
// 此函数获取列表的头指针,要旋转的子列表的起始点和结束点以及数字k,并将子列表向右旋转k个位置。
void rotateSubList(ListNode* A, int m, int n, int k)
{
int size = n - m + 1;
// 如果k大于子列表的大小,则我们将使用它的模数
if (k > size) {
k = k % size;
}
// 如果k为零或k等于大小或k是
// 子列表的大小的倍数,那么列表保持不变
if (k == 0 || k == size) {
ListNode* head = A;
while (head != NULL) {
cout << head->data;
head = head->next;
}
return;
}
ListNode* link = NULL; // 第m个节点
if (m == 1) {
link = A;
}
// 此循环将遍历所有节点直到子列表的结束节点。
ListNode* c = A; // 当前遍历的节点
int count = 0; // 遍历节点的计数
ListNode* end = NULL;
ListNode* pre = NULL; // m-th节点的上一个节点
while (c != NULL) {
count++;
// 我们将保存(m-1)个节点,然后
// 让它指向(n-k+1)个节点
if (count == m - 1) {
pre = c;
link = c->next;
}
if (count == n - k) {
if (m == 1) {
end = c;
A = c->next;
}
else {
end = c;
// 这就是我们将第(n-k+1)个
// 节点带到子列表前面的方法。
pre->next = c->next;
}
}
// 这将保持列表的剩余部分不变。
if (count == n) {
ListNode* d = c->next;
c->next = link;
end->next = d;
ListNode* head = A;
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
return;
}
c = c->next;
}
}
// 创建和链接新节点的函数
void push(struct ListNode** head, int val)
{
struct ListNode* new_node = new ListNode;
new_node->data = val;
new_node->next = (*head);
(*head) = new_node;
}
// 驱动器代码
int main()
{
struct ListNode* head = NULL;
push(&head, 70);
push(&head, 60);
push(&head, 50);
push(&head, 40);
push(&head, 30);
push(&head, 20);
push(&head, 10);
ListNode* tmp = head;
cout << "给出的列表:";
while (tmp != NULL) {
cout << tmp->data << " ";
tmp = tmp->next;
}
cout << endl;
int m = 3, n = 6,k = 2;
cout << "子列表旋转后:";
rotateSubList(head, m, n, k);
return 0;
}
输出:
给出的列表:10 20 30 40 50 60 70
子列表旋转后:10 20 50 60 30 40 70
时间复杂度 :O(n),其中n为给定链表中的节点数
辅助空间: O(1)