การจัดเรียงสลับกันของ Linked List ใน C++

บทนำ

จัดเรียง Linked List แบบ Alternate: โหนดแรก = ค่าน้อยสุด, โหนดที่สอง = ค่ามากสุด, โหนดที่สาม = ค่าน้อยสุดอันดับ 2, ...

ตัวอย่าง

Input: 3→4→21→67→1→8 → Sorted: 1→3→4→8→21→67 → Alternate: 1→67→3→21→4→8

อัลกอริทึม

1. เรียง Linked List ด้วย Merge Sort
2. แบ่งเป็นสองครึ่ง (Front/Back split)
3. กลับด้านครึ่งหลัง (Reverse)
4. Merge ทั้งสองครึ่งสลับกัน (Alternate Merge)

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

#include <bits/stdc++.h>
using namespace std;

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

Node* getNode(int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// ... (Merge Sort, FrontBackSplit, SortedMerge, Reverse, AlternateMerge functions)

Node* altSortLinkedList(Node* head) {
    // Merge Sort
    // FrontBackSplit
    // Reverse back half
    // Alternate Merge
    return front; // head of result
}

int main() {
    Node* head = getNode(3);
    head->next = getNode(4);
    head->next->next = getNode(21);
    head->next->next->next = getNode(67);
    head->next->next->next->next = getNode(1);
    head->next->next->next->next->next = getNode(8);
    
    cout << "Initial list: "; printList(head);
    head = altSortLinkedList(head);
    cout << "\nSorted list: "; printList(head);
    return 0;
}

ผลลัพธ์

Initial list: 3 4 21 67 1 8
Sorted list: 1 67 3 21 4 8