โปรแกรมสลับโหนดในลิงก์ลิสต์แบบคู่ใน C++

สมมติว่าเรามีลิงก์ลิสต์ เราต้องสลับโหนดที่อยู่ติดกันเป็นคู่ (pair) และคืนหัวลิสต์ โดยมีเงื่อนไขว่าไม่สามารถแก้ไขค่าของโหนดได้ ต้องเปลี่ยนโหนดเอง เช่น [1,2,3,4] กลายเป็น [2,1,4,3]

ขั้นตอนการแก้ปัญหา

1. ถ้า head ไม่มี คืนค่า head
2. first = head, second = head.next, สร้าง dummy ค่า -1
3. dummy.next = first, prev = dummy
4. วนลูป while second ไม่ใช่ NULL:
   • temp = second.next
   • first.next = second.next
   • second.next = first
   • prev.next = second
   • prev = first
   • ถ้า temp ไม่ใช่ NULL: first = temp, second = temp.next มิฉะนั้น break
5. คืนค่า dummy.next

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

#include 
using namespace std;

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

ListNode* make_list(vector 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) {
    ListNode *ptr = 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 v = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    ListNode *head = make_list(v);
    print_list(ob.swapPairs(head));
    // Output: [2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, ]
}

อินพุต / เอาต์พุต

Input: {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

Output: [2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, ]