Kiểm tra danh sách liên kết có sắp xếp theo cặp C++

Danh sách pairwise sorted: các cặp liên tiếp (a₁,a₂), (a₃,a₄)... đều có aᵢ ≤ aᵢ₊₁. Phần tử lẻ cuối cùng bỏ qua.

Ví dụ: {8, 10, 18, 20, 5, 15} → cặp (8,10), (18,20), (5,15) đều tăng → pairwise sorted.

Giải thuật

Duyệt danh sách, mỗi bước kiểm tra cặp hiện tại: nếu data > next->data → false. Nhảy 2 nút mỗi lần.

Ví dụ minh họa

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

void append(Node** start, int key) {
    Node* new_node = new Node;
    new_node->data = key;
    new_node->next = *start;
    *start = new_node;
}

bool isPairwiseSorted(Node* start) {
    Node* temp = start;
    while (temp && temp->next) {
        if (temp->data > temp->next->data)
            return false;
        temp = temp->next->next;
    }
    return true;
}

int main() {
    Node* start = NULL;
    int arr[] = {8, 10, 18, 20, 5, 15};
    int n = sizeof(arr)/sizeof(arr[0]);
    for (int i = 0; i < n; i++) append(&start, arr[i]);
    
    if (isPairwiseSorted(start))
        cout << "Day la pairwise sorted";
    else
        cout << "Day KHONG phai pairwise sorted";
}

Kết quả

Day la pairwise sorted