C++ สลับคู่โหนดใน Linked List แบบคู่ๆ (Pairwise Swap)

เพื่อแก้ปัญหาที่เราต้องสลับโหนดคู่ๆ (Pairwise) ใน Linked List แล้วพิมพ์ออกมา เช่น

Input : 1->2->3->4->5->6->NULL Output : 2->1->4->3->6->5->NULL
Input : 1->2->3->4->5->NULL Output : 2->1->4->3->5->NULL
Input : 1->NULL Output : 1->NULL

มีสองวิธีแก้ปัญหา ทั้งสองมีความซับซ้อนด้านเวลา O(N) โดย N คือขนาด Linked List ตอนนี้เราจะสำรวจทั้งสองวิธี

วิธี Iterative (วนซ้ำ)

ในวิธีนี้ เราจะวนลูปผ่านสมาชิกของ Linked List และสลับคู่ๆ จนกว่าจะถึง NULL

ตัวอย่าง

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

class Node { 
public: 
    int data; 
    Node* next; 
}; 

void swapPairwise(Node* head){ 
    Node* temp = head; 
    while (temp != NULL && temp->next != NULL) { 
        swap(temp->data, temp->next->data); 
        temp = temp->next->next; 
    } 
} 

void push(Node** head_ref, int new_data){ 
    Node* new_node = new Node(); 
    new_node->data = new_data; 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 

void printList(Node* node){ 
    while (node != NULL) { 
        cout << node->data << " "; 
        node = node->next; 
    } 
} 

int main(){ 
    Node* head = NULL; 
    push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); 
    cout << "Linked list before\n"; printList(head); 
    swapPairwise(head); 
    cout << "\nLinked list after\n"; printList(head); 
    return 0; 
}

ผลลัพธ์

Linked list before 1 2 3 4 5
Linked list after 2 1 4 3 5

เราจะใช้ตรรกะเดียวกันในวิธีถัดไป แต่จะวนลูปแบบ Recursive แทน

วิธี Recursive (การเรียกซ้ำ)

ในวิธีนี้ เราใช้ตรรกะเดียวกันแต่ใช้ Recursion

ตัวอย่าง

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

class Node { 
public: 
    int data; 
    Node* next; 
}; 

void swapPairwise(struct Node* head){ 
    if (head != NULL && head->next != NULL) { 
        swap(head->data, head->next->data); 
        swapPairwise(head->next->next); 
    } 
    return; 
} 

void push(Node** head_ref, int new_data){ 
    Node* new_node = new Node(); 
    new_node->data = new_data; 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 

void printList(Node* node){ 
    while (node != NULL) { 
        cout << node->data << " "; 
        node = node->next; 
    } 
} 

int main(){ 
    Node* head = NULL; 
    push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); 
    cout << "Linked list before\n"; printList(head); 
    swapPairwise(head); 
    cout << "\nLinked list after\n"; printList(head); 
    return 0; 
}

ผลลัพธ์

Linked list before 1 2 3 4 5
Linked list after 2 1 4 3 5

คำอธิบายโค้ด

ในวิธีนี้ เราเดินผ่าน Linked List แบบคู่ๆ ตอนที่เจอคู่ เราสลับข้อมูลของพวกเขาและไปคู่ถัดไป ซึ่งเป็นวิธีที่โปรแกรมทำงานในทั้งสองวิธี

สรุป

ในบทช่วยสอนนี้ เราแก้ปัญหา Pairwise swap elements of a given linked list โดยใช้ Recursion และ Iteration เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์