Đếm số lần xoay trong danh sách liên kết đã sắp xếp và xoay trong C++

Cho một danh sách liên kết. Danh sách này được sắp xếp trước rồi xoay K nút. Mục tiêu là tìm giá trị K.

Ví dụ: Danh sách đầu vào: 5 → 7 → 9 → 1 → 3. Danh sách gốc đã sắp xếp: 1 → 3 → 5 → 7 → 9. Ta thấy K = 3 (xoay 3 lần từ danh sách gốc).

Ví dụ

Đầu vào: List: 5 → 7 → 9 → 1 → 3
Đầu ra: 3

Đầu vào: List: 17 → 25 → 62 → 99
Đầu ra: 4 (danh sách đã sắp xếp, xoay một vòng tròn đầy đủ).

Giải thuật

Danh sách liên kết đầu vào sẽ có một điểm mà nút tiếp theo nhỏ hơn nút trước. Nếu danh sách cũng đã sắp xếp thì nó là xoay đầy đủ một vòng. Duyệt từ nút đầu, đếm số nút liên tiếp có giá trị lớn hơn giá trị nút đầu. Khi gặp nút có giá trị nhỏ hơn nút đầu, dừng lại. Số đếm được chính là K.

• Hàm insert_node chèn nút vào đầu danh sách.
• Hàm print in danh sách.
• Hàm rotations(struct List_Node* head) trả về số lần xoay.

Ví dụ triển khai

#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;
}

Kết quả

Elements in the linked list are: 28 35 18 1 2
Count of rotations in sorted and rotated linked list are: 2