Sắp xếp thay thế danh sách liên kết trong C++

Sắp xếp danh sách liên kết đơn theo kiểu thay thế: node 1 là min, node 2 là max, node 3 là min thứ 2, node 4 là max thứ 2,...

Ví dụ: 3→4→21→67→1→8 -> Sorted: 1→67→3→21→4→8.

Thuật toán:

1. Sắp xếp linked list bằng Merge Sort.
2. Chia list thành 2 nửa (FrontBackSplit).
3. Đảo nửa sau (reverse).
4. Trộn 2 nửa luân phiên (alternateMerge).

Ví dụ code (tóm tắt)

struct Node { int data; Node* next; };
// MergeSort, FrontBackSplit, SortedMerge, reverse, alternateMerge, altSortLinkedList
// Xem code đầy đủ trong nội dung gốc.
int main() {
    Node* head = ... // 3 4 21 67 1 8
    head = altSortLinkedList(head);
    printList(head); // 1 67 3 21 4 8
}

Kết quả

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