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

ในบทความนี้ เราต้องการกลับลิงก์ (links) ด้วยการใช้ Singly Linked List งานของเราคือสร้างฟังก์ชันที่สามารถกลับ Singly Linked List ที่กำหนดได้ เช่น:

Input: Following Linked list : 1→2→3→4→NULL 
Output: After processing of our function: 4→3→2→1→NULL

แนวทางแก้ปัญหา

มีหลายวิธีในการกลับ Linked List โดยทั่วไปวิธีที่ง่ายคือเดินผ่านลิสต์และกลับมันขณะเดิน

วิธีที่ 1: วิธีง่าย (Iterative - 3 Pointers)

เราจะเดินผ่าน Linked List และกลับลิงก์ขณะเดิน

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

struct Node {
    int data;
    struct Node* next;
    Node(int data) {
        this->data = data;
        next = NULL;
    }
};

struct LinkedList {
    Node* head;
    LinkedList() { head = NULL; }
    
    // Function to reverse linked list
    void reverse() {
        auto curr = head;      // current pointer
        Node* prev = NULL;     // previous pointer
        
        while (curr) {
            auto temp = curr->next;
            curr->next = prev;
            prev = curr;
            head = prev;
            curr = temp;
        }
    }
    
    void print() {
        struct Node* temp = head;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
    }
    
    void push(int data) {
        Node* temp = new Node(data);
        temp->next = head;
        head = temp;
    }
};

int main() {
    LinkedList list;
    list.push(20);
    list.push(4);
    list.push(15);
    list.push(85);
    list.print();
    list.reverse();
    cout << "\n";
    list.print();
}

ผลลัพธ์

85 15 4 20 
20 4 15 85

วิธีนี้มี Time Complexity เป็น O(N) โดยที่ N คือขนาดของลิสต์

วิธีที่ 2: ใช้ Stack

เราจะใช้ Stack เก็บโหนดทั้งหมด แล้วกลับลิสต์โดยการ Pop จาก Stack

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

struct Node {
    int data;
    struct Node* next;
    Node(int data) {
        this->data = data;
        next = NULL;
    }
};

struct LinkedList {
    Node* head;
    LinkedList() { head = NULL; }
    
    void reverse() {
        auto curr = head;
        stack<Node*> s;
        
        while (curr) {
            s.push(curr);
            curr = curr->next;
        }
        
        Node* prev = s.top();
        head = prev;
        s.pop();
        
        while (!s.empty()) {
            auto temp = s.top();
            s.pop();
            prev->next = temp;
            prev = temp;
        }
        prev->next = NULL;
    }
    
    void print() {
        struct Node* temp = head;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
    }
    
    void push(int data) {
        Node* temp = new Node(data);
        temp->next = head;
        head = temp;
    }
};

int main() {
    LinkedList list;
    list.push(20);
    list.push(4);
    list.push(15);
    list.push(85);
    list.print();
    list.reverse();
    cout << "\n";
    list.print();
}

ผลลัพธ์

85 15 4 20 
20 4 15 85

วิธีที่ 3: ใช้ Recursion (เวียนเกิด)

ในวิธีนี้ เราทำกระบวนการเดียวกันแต่ใช้ Recursive Calls

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

struct Node {
    int data;
    struct Node* next;
    Node(int data) {
        this->data = data;
        next = NULL;
    }
};

struct LinkedList {
    Node* head;
    LinkedList() { head = NULL; }
    
    void rreverse(Node* curr, Node* prev) {
        if (curr == NULL) {
            head = prev;
            return;
        }
        rreverse(curr->next, curr);
        curr->next = prev;
    }
    
    void reverse() {
        auto curr = head;
        Node* prev = NULL;
        rreverse(curr, prev);
    }
    
    void print() {
        struct Node* temp = head;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
    }
    
    void push(int data) {
        Node* temp = new Node(data);
        temp->next = head;
        head = temp;
    }
};

int main() {
    LinkedList list;
    list.push(20);
    list.push(4);
    list.push(15);
    list.push(85);
    list.print();
    list.reverse();
    cout << "\n";
    list.print();
}

ผลลัพธ์

85 15 4 20 
20 4 15 85

วิธีนี้ก็มี Time Complexity เป็น O(N) เช่นกัน

สรุป

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