กลับ Doubly Linked List ด้วย C++

ในบทความนี้ เรามี Doubly Linked List และจะอธิบายวิธีการกลับมันใน C++ เช่น:

Input : {1, 2, 3, 4} 
Output : {4, 3, 2, 1}

โดยทั่วไปมีวิธีหนึ่งที่คิดได้ง่าย แต่เราจะใช้ 2 วิธี − วิธีปกติและวิธีที่ไม่ธรรมดา

วิธีที่ 1: วิธีปกติ (Normal Approach)

ในวิธีนี้ เราจะเดินผ่านลิสต์ และกลับลิงก์ขณะเดิน

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

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

void reverse(Node** head_ref) {
    auto temp = (*head_ref)->next;
    (*head_ref)->next = (*head_ref)->prev;
    (*head_ref)->prev = temp;
    
    if (temp != NULL) {
        (*head_ref) = (*head_ref)->prev;
        reverse(head_ref);
    } else
        return;
}

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

int main() {
    Node* head = NULL;
    push(&head, 6);
    push(&head, 4);
    push(&head, 8);
    push(&head, 9);
    
    auto node = head;
    cout << "Before\n";
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << "\n";
    
    reverse(&head);
    
    node = head;
    cout << "After\n";
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    return 0;
}

ผลลัพธ์

Before 
9 8 4 6 
After 
6 4 8 9

วิธีนี้ใช้ Time Complexity O(N) ซึ่งดีมากสำหรับข้อจำกัดที่สูง

วิธีที่ 2: วิธีที่ไม่ธรรมดา (ใช้ Stack)

ในวิธีนี้ เราจะสร้าง Stack เก็บโหนดขณะเดิน แล้ว Pop ออกมาและเปลี่ยนค่าเพื่อกลับลิสต์

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

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

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

int main() {
    Node* head = NULL;
    push(&head, 6);
    push(&head, 4);
    push(&head, 8);
    push(&head, 9);
    
    auto node = head;
    cout << "Before\n";
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << "\n";
    
    stack<Node*> s;
    node = head;
    while (node) {
        head = node;
        s.push(node);
        node = node->next;
    }
    
    while (!s.empty()) {
        auto x = s.top();
        auto temp = x->prev;
        x->prev = x->next;
        x->next = temp;
        s.pop();
    }
    
    node = head;
    cout << "After\n";
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    return 0;
}

ผลลัพธ์

Before 
9 8 4 6 
After 
6 4 8 9

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

ในวิธีนี้ เราใช้ Stack เก็บโหนดขณะเดินผ่านลิสต์ แล้ว Pop ออกมาและสลับ next กับ prev ของแต่ละโหนด Time Complexity คือ O(N) เหมาะสำหรับข้อจำกัดสูงเช่นกัน

สรุป

ในบทความนี้ เราแก้ปัญหาการกลับ Doubly Linked List ด้วยและไม่ใช้ Stack ใน O(N) โดยที่ N คือขนาดของลิสต์ เรียนรู้โปรแกรม C++ และแนวทาง 2 วิธี (ปกติและไม่ธรรมดา) สามารถเขียนในภาษาอื่นได้เช่น C, Java, Python หวังว่าจะเป็นประโยชน์