資料結構
網路
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 次檢視
