แยก Linked List แบบ Odd-Even Index ใน C++

โจทย์

กำหนด Singly Linked List จัดเรียงใหม่ให้โหนด Index คี่ (1,3,5...) อยู่หน้า โหนด Index คู่ (2,4,6...) อยู่หลัง โดยรักษาลำดับภายในกลุ่ม

ตัวอย่าง

Input: 2 → 1 → 3 → 8 → 5 (Index: 1,2,3,4,5)

Output: 2 → 3 → 5 → 1 → 8 (Odd: 2,3,5 | Even: 1,8)

แนวคิด: 3 Pointers

• odd: ชี้โหนดคี่ปัจจุบัน
• even: ชี้โหนดคู่ปัจจุบัน
• evenHead: จำจุดเริ่มต้นของกลุ่มคู่ (เพื่อต่อท้ายกลุ่มคี่)

โค้ด C++

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* oddEvenList(ListNode* head) {
    if (!head || !head->next) return head;
    
    ListNode* odd = head;
    ListNode* even = head->next;
    ListNode* evenHead = even;
    
    while (even && even->next) {
        odd->next = even->next;   // odd ชี้ไปโหนดคี่ถัดไป
        odd = odd->next;          // ขยับ odd
        even->next = odd->next;   // even ชี้ไปโหนดคู่ถัดไป
        even = even->next;        // ขยับ even
    }
    
    odd->next = evenHead;         // ต่อกลุ่มคู่ท้ายกลุ่มคี่
    return head;
}

// Helper functions
void insertAtHead(ListNode*& head, int val) {
    ListNode* n = new ListNode(val);
    n->next = head;
    head = n;
}

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

int main() {
    ListNode* head = nullptr;
    // สร้าง: 2 -> 1 -> 3 -> 8 -> 5 (insert at head → reversed order)
    insertAtHead(head, 5);
    insertAtHead(head, 8);
    insertAtHead(head, 3);
    insertAtHead(head, 1);
    insertAtHead(head, 2);
    
    cout << "Original: ";
    printList(head);
    
    head = oddEvenList(head);
    
    cout << "Odd-Even: ";
    printList(head);
    
    return 0;
}

การทำงานแบบ Step-by-Step

Initial:  odd=2, even=1, evenHead=1
          List: 2 → 1 → 3 → 8 → 5

Iter 1: odd->next = 3 (even->next), odd=3
        even->next = 8 (odd->next), even=8
        List: 2 → 3 → ...   1 → 8 → ...

Iter 2: odd->next = 5 (even->next), odd=5
        even->next = null (odd->next), even=null
        List: 2 → 3 → 5 → ...   1 → 8 → null

Final:  odd->next = evenHead (1)
        Result: 2 → 3 → 5 → 1 → 8

Complexity

• Time: O(n) - Single pass
• Space: O(1) - In-place, ไม่ใช้ Extra space

ผลลัพธ์

Original: 2 -> 1 -> 3 -> 8 -> 5
Odd-Even: 2 -> 3 -> 5 -> 1 -> 8

สรุป

Technique แยก Odd-Even ใช้ 3 pointers ทำใน O(n) time, O(1) space เป็น Classic Linked List Problem ที่พบบ่อยใน Interview (LeetCode 328)