Sắp xếp node chẵn lẻ xen kẽ trong danh sách liên kết đơn trong C++

Sắp xếp lại linked list sao cho node chẵn và lẻ xen kẽ nhau (dữ liệu node). Có 2 dạng: bắt đầu bằng chẵn hoặc bắt đầu bằng lẻ.

Ví dụ: 45→21→2→213→3→34→78→12 -> Kết quả: 45→2→21→34→213→78→3→12 (giả sử bắt đầu bằng lẻ).

Cách làm (dùng stack):

• Duyệt list, nếu node lẻ ở vị trí chẵn (index chẵn, 0-based) -> push vào stack odd.
• Nếu node chẵn ở vị trí lẻ -> push vào stack even.
• Sau duyệt, pop từ 2 stack, hoán đổi dữ liệu 2 node.

Ví dụ code

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

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

void OddEvenList(Node* head) {
    stack<Node*> odd, even;
    int i = 1; // vị trí 1-based
    while (head) {
        if (head->data % 2 != 0 && i % 2 == 0) odd.push(head);
        else if (head->data % 2 == 0 && i % 2 != 0) even.push(head);
        head = head->next; i++;
    }
    while (!odd.empty() && !even.empty()) {
        swap(odd.top()->data, even.top()->data);
        odd.pop(); even.pop();
    }
}

Kết quả

Linked List: 12 78 34 3 213 2 21 45
Linked List after Rearranging: 3 78 45 12 213 2 21 34