数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中排序并旋转链表的旋转次数统计
给定一个链表。该列表首先排序，然后旋转 K 个节点。目标是找到 K 的值。如果我们给定以下链表作为输入，它被旋转了 K 个节点 -
那么原来的链表应该是 -
我们可以看到这里的 K 是 2。输入链表是原始排序链表中旋转 2 个节点的结果。
让我们通过例子来理解。
输入 - 列表：5 → 7 → 9 → 1 → 3
输出
链表中的元素为：5 7 9 1 3
排序并旋转链表的旋转次数为 - 3
说明 - 我们可以在原始排序列表中旋转三次后得到输入列表。
1 → 3 → 5 → 7 → 9, original 9 → 1 → 3 → 5 → 7, rotation 1 7 → 9 → 1 → 3 → 5, rotation 2 5 → 7 → 9 → 1 → 3 rotation 3
输入 - 列表 - 17 → 25 → 62 → 99
输出
链表中的元素为 - 17 25 62 99
排序并旋转链表的旋转次数为 - 4
说明 - 我们可以在原始排序列表中旋转四次后得到输入列表。
17 → 25 → 62 → 99, original 99 → 17 → 25 → 62, rotation 1 62 → 99 → 17 → 25, rotation 2 25 → 62 → 99 → 17, rotation 3 17 → 25 → 62 → 99, rotation 4
下面程序中使用的方法如下
输入链表将有一个点，其中下一个节点小于前一个节点。如果输入字符串也是排序的，则它是原始字符串的完整旋转。从头节点开始遍历，直到（当前节点的数据 > 头节点的数据）并递增计数。在（当前节点的数据 < 头节点的数据）的情况下，中断循环。计数将包含原始列表中获取输入列表的旋转次数。
获取输入列表并在其中插入元素。
函数 insert_node(struct List_Node** head, int data) 在带有数据的单链表的头部插入节点。
函数 print(struct List_Node* node) 使用 while 循环打印从头到尾的输入链表。
函数 rotations(struct List_Node* head) 获取链表的头指针并返回原始链表中完成的旋转次数以获取输入链表。
将初始计数设置为 0。
将 temp 变量作为头节点的数据部分。
使用 while 循环，遍历直到到达链表的末尾。（head!=NULL）。
如果每个当前节点的数据都大于 temp，则递增计数。
如果当前节点的数据小于头节点的数据（temp）。中断，
我们将计算旋转次数。
返回计数作为结果。
示例
#include <bits/stdc++.h>
using namespace std;
struct List_Node{
int data;
struct List_Node* next;
};
int rotations(struct List_Node* head){
int count = 0;
int temp = head->data;
while (head != NULL){
if (temp > head->data){
break;
}
count++;
head = head->next;
}
return count;
}
void insert_node(struct List_Node** head, int data){
struct List_Node* new_node = new List_Node;
new_node->data = data;
new_node->next = (*head);
(*head) = new_node;
}
void print(struct List_Node* node){
while (node != NULL){
cout<<node->data<<" ";
node = node->next;
}
}
int main(){
struct List_Node* head = NULL;
insert_node(&head, 2);
insert_node(&head, 1);
insert_node(&head, 18);
insert_node(&head, 35);
insert_node(&head, 28);
cout<<"Elements in the linked list are: ";
print(head);
cout<<"\nCount of rotations in sorted and rotated linked list are: "<<rotations(head);
return 0;
}输出
如果我们运行以上代码，它将生成以下输出 -
Elements in the linked list are: 28 35 18 1 2 Count of rotations in sorted and rotated linked list are: 2
129 次查看
