จัดเรียงโหนดคี่-คู่สลับกันใน Singly Linked List ใน C++

บทนำ

จัดเรียง Singly Linked List ให้สลับระหว่างเลขคี่และเลขคู่ (Odd-Even Alternating)

มี 2 รูปแบบ:

1. เริ่มด้วยเลขคู่: Even, Odd, Even, Odd, ...
2. เริ่มด้วยเลขคี่: Odd, Even, Odd, Even, ...

ตัวอย่าง

Input: 45→21→2→213→3→34→78→12 → Output: 45→2→21→34→213→78→3→12

แนวคิด (ใช้ Stack)

1. สร้าง stack สองอัน: oddStack, evenStack
2. วนลูป Linked List:
   • ถ้าเจอเลขคี่ในตำแหน่งคู่ (0-indexed) → push ลง oddStack
   • ถ้าเจอเลขคู่ในตำแหน่งคี่ → push ลง evenStack
3. Pop จากทั้งสอง stack มาสลับกัน (swap data)

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

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

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

void OddEvenList(Node* head) {
    stack odd, even;
    int i = 1; // 1-indexed position
    while (head != nullptr) {
        if (head->data % 2 != 0 && i % 2 == 0) // odd at even pos
            odd.push(head);
        else if (head->data % 2 == 0 && i % 2 != 0) // even at odd pos
            even.push(head);
        head = head->next;
        i++;
    }
    while (!odd.empty() && !even.empty()) {
        swap(odd.top()->data, even.top()->data);
        odd.pop(); even.pop();
    }
}

ผลลัพธ์

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