จัดเรียงโหนดสระและพยัญชนะใน Linked List (C++)

โจทย์ปัญหา

ได้รับ Linked List ที่แต่ละโหนดเก็บตัวอักษร ให้จัดเรียงใหม่โดยย้ายโหนดที่เป็น สระ (Vowels) ไปอยู่ข้างหน้า และ พยัญชนะ (Consonants) ไปอยู่ข้างหลัง รักษาลำดับเดิมภายในแต่ละกลุ่ม (Stable)

ตัวอย่าง

นำเข้า: A → M → A → Z → O → N
ผลลัพธ์: A → A → O → M → Z → N

แนวคิดการแก้ปัญหา (Two Lists + Merge)

1. สร้าง Dummy Heads 2 ตัว: vowelHead, consonantHead
2. เดินผ่าน List เดิม แยกโหนดไปสอง List:
   • ถ้าเป็นสระ → ต่อท้าย vowelList
   • ถ้าเป็นพยัญชนะ → ต่อท้าย consonantList
3. ต่อ vowelList ต่อกับ consonantList
4. คืน Head ใหม่

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

#include <iostream>
using namespace std;

struct Node {
    char data;
    Node* next;
    Node(char d) : data(d), next(nullptr) {}
};

bool isVowel(char c) {
    c = toupper(c);
    return c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}

Node* groupByVowels(Node* head) {
    Node vowelDummy('V'), consonantDummy('C');
    Node *vowelTail = &vowelDummy, *consonantTail = &consonantDummy;

    for (Node* curr = head; curr != nullptr; ) {
        Node* next = curr->next;
        curr->next = nullptr;

        if (isVowel(curr->data)) {
            vowelTail->next = curr;
            vowelTail = curr;
        } else {
            consonantTail->next = curr;
            consonantTail = curr;
        }
        curr = next;
    }

    // Merge: Vowels first, then Consonants
    vowelTail->next = consonantDummy.next;
    Node* newHead = vowelDummy.next;

    // Cleanup dummies (optional)
    return newHead;
}

Node* createList(const string& s) {
    if (s.empty()) return nullptr;
    Node* head = new Node(s[0]);
    Node* curr = head;
    for (size_t i = 1; i < s.size(); i++) {
        curr->next = new Node(s[i]);
        curr = curr->next;
    }
    return head;
}

void printList(Node* head) {
    while (head) {
        cout << head->data;
        if (head->next) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    string input = "AMAZON";
    Node* head = createList(input);
    cout << "Original: ";
    printList(head);

    head = groupByVowels(head);
    cout << "After grouping: ";
    printList(head);

    return 0;
}

ผลลัพธ์

Original: A -> M -> A -> Z -> O -> N
After grouping: A -> A -> O -> M -> Z -> N

Complexity Analysis

• Time: O(n) - เดินผ่าน List 1 ครั้ง
• Space: O(1) - ใช้ Pointer คงที่ ไม่สร้าง Node ใหม่ (แค่ย้าย Pointer)

คำอธิบายเพิ่มเติม

• Technique นี้เรียกว่า Partitioning (คล้าย QuickSort Partition)
• รักษา Relative Order (Stable) - สระที่มาก่อนยังอยู่ก่อน, พยัญชนะที่มาก่อนยังอยู่ก่อน
• Dummy Nodes ช่วยลด Special Cases (Empty List, All Vowels, All Consonants)
• ขยายได้: แยกตามเงื่อนไขอื่นๆ เช่น Odd/Even, Positive/Negative