นับจำนวนการหมุนเวียนใน Linked List ที่เรียงลำดับแล้วหมุนใน C++

เราได้รับ Linked List ที่เรียงลำดับก่อน แล้วค่อยหมุนเวียน (rotate) ไป K โหนด เป้าหมายคือหาค่า K

ตัวอย่าง

อินพุต: List: 5 → 7 → 9 → 1 → 3

เอาต์พุต: 3

คำอธิบาย: รายการต้นฉบับคือ 1 → 3 → 5 → 7 → 9 หมุน 3 ครั้งจะได้รายการที่รับเข้ามา

1 → 3 → 5 → 7 → 9 (ต้นฉบับ)
9 → 1 → 3 → 5 → 7 (หมุน 1)
7 → 9 → 1 → 3 → 5 (หมุน 2)
5 → 7 → 9 → 1 → 3 (หมุน 3)

อินพุต: List: 17 → 25 → 62 → 99

เอาต์พุต: 4

คำอธิบาย: หมุน 4 ครั้ง (เท่ากับจำนวนโหนด) จะกลับมาเป็นเดิม

แนวทางการแก้ปัญหา

Linked List ที่รับเข้ามาจะมีจุดหนึ่งที่โหนดถัดไปมีค่าน้อยกว่าโหนดก่อนหน้า หากรายการเรียงลำดับสมบูรณ์ แสดงว่าเป็นการหมุนเต็มรอบ เริ่มจาก head node วนลูปจนกว่า (ค่าโหนดปัจจุบัน > ค่า head node) นับจำนวนรอบ เมื่อเจอค่าน้อยกว่า head ให้หยุด

การนำไปใช้ (Implementation)

#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