ตรวจสอบ Linked List ว่าเป็น Pairwise Sorted ใน C++

Pairwise Sorted คืออะไร?

Linked List ถือว่า Pairwise Sorted หากทุกคู่ที่อยู่ติดกัน (index 0-1, 2-3, 4-5, ...) มีลำดับจากน้อยไปมาก

ตัวอย่าง: [8, 10, 18, 20, 5, 15] → คู่: (8,10)✓, (18,20)✓, (5,15)✓ → Pairwise Sorted

ถ้าจำนวนโหนดคี่ โหนดสุดท้ายไม่นับ

อัลกอริทึม

1. ท่อง Linked List ทีละคู่ (กระโดด 2 โหนดต่อรอบ)
2. ตรวจสอบว่า current->data ≤ current->next->data
3. ถ้ามีคู่ใดไม่เรียง → return false
4. จบลูป → return true

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

void append(Node** head, int data) {
    Node* newNode = new Node{data, *head};
    *head = newNode;
}

bool isPairwiseSorted(Node* head) {
    Node* curr = head;
    while (curr != nullptr && curr->next != nullptr) {
        if (curr->data > curr->next->data)
            return false; // ไม่เรียง
        curr = curr->next->next; // กระโดดไปคู่ถัดไป
    }
    return true;
}

int main() {
    Node* head = nullptr;
    int arr[] = {8, 10, 18, 20, 5, 15};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    // สร้าง list (จะได้ลำดับย้อนกลับ)
    for (int i = n-1; i >= 0; i--)
        append(&head, arr[i]);
    
    if (isPairwiseSorted(head))
        cout << "List is pairwise sorted" << endl;
    else
        cout << "List is NOT pairwise sorted" << endl;
    
    // ทดสอบกรณีไม่เรียง
    Node* head2 = nullptr;
    int arr2[] = {10, 8, 20, 18}; // (10,8) ไม่เรียง
    for (int i = 3; i >= 0; i--)
        append(&head2, arr2[i]);
    
    if (isPairwiseSorted(head2))
        cout << "List2 is pairwise sorted" << endl;
    else
        cout << "List2 is NOT pairwise sorted" << endl;
    
    return 0;
}

ผลลัพธ์

List is pairwise sorted
List2 is NOT pairwise sorted

ความซับซ้อน

• เวลา: O(n) - ท่องครั้งเดียว
• พื้นที่: O(1) - ใช้ pointer คงที่

หมายเหตุ

โค้ดต้นฉบับมี bug: `if (temp->data < temp->next->data) flag = false;` ควรเป็น `>` เพราะเราต้องการ ascending order