การสลับโหนดคู่ใน Linked List (Swap Nodes in Pairs) ใน C++

โจทย์ปัญหา

ได้รับ Linked List ให้สลับโหนดที่อยู่ติดกันเป็นคู่ๆ (1↔2, 3↔4, ...) และคืนค่า Head ใหม่ ห้ามเปลี่ยนค่าในโหนด ต้องสลับโหนดเอง

ตัวอย่าง

นำเข้า: [1,2,3,4,5,6,7,8]
ผลลัพธ์: [2,1,4,3,6,5,8,7]

แนวคิดการแก้ปัญหา

ใช้ Dummy Node ช่วยจัดการ Head node ได้ง่ายขึ้น และใช้ Pointer 3 ตัว:

• prev - โหนดก่อนคู่ที่กำลังสลับ
• first - โหนดแรกของคู่
• second - โหนดที่สองของคู่

ขั้นตอนการสลับคู่เดียว:

1. temp = second->next (เก็บโหนดถัดไป)
2. first->next = second->next
3. second->next = first
4. prev->next = second
5. อัปเดต prev = first, first = temp, second = temp ? temp->next : nullptr

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

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

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int data) : val(data), next(NULL) {}
};

ListNode* make_list(vector<int> v) {
    ListNode *head = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ListNode *ptr = head;
        while (ptr->next != NULL) ptr = ptr->next;
        ptr->next = new ListNode(v[i]);
    }
    return head;
}

void print_list(ListNode *head) {
    cout << "[";
    while (ptr->next) {
        cout << ptr->val << ", ";
        ptr = ptr->next;
    }
    cout << "]" << endl;
}

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head) return head;
        ListNode* first = head;
        ListNode* second = head->next;
        ListNode* dummy = new ListNode(-1);
        dummy->next = first;
        ListNode* prev = dummy;

        while (second) {
            ListNode* temp = second->next;
            first->next = second->next;
            second->next = first;
            prev->next = second;
            prev = first;
            if (temp) {
                first = temp;
                second = temp->next;
            } else break;
        }
        return dummy->next;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3,4,5,6,7,8};
    ListNode *head = make_list(v);
    print_list(ob.swapPairs(head));
    return 0;
}

ผลลัพธ์

[2,1,4,3,6,5,8,7]

คำอธิบายเพิ่มเติม

• ความซับซ้อนด้านเวลา: O(n)
• ความซับซ้อนด้านพื้นที่: O(1) (In-place)
• Dummy node ช่วยลด special case สำหรับ head node