ลบโหนดสุดท้ายของ Linked List ใน C++

เราได้รับ Singly Linked List และมีงานให้ลบโหนดสุดท้ายออกจากลิสต์นั้น ในปัญหานี้ เราจะเดินผ่านลิสต์ที่กำหนดและลบโหนดสุดท้ายอย่างง่าย

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

ในวิธีนี้ เราเดินผ่านลิสต์ที่กำหนด และติดตามโหนดก่อนหน้า (previous) และโหนดปัจจุบัน (current) ตอนที่โหนดปัจจุบันกลายเป็นโหนดสุดท้าย เราเปลี่ยน previous->next เป็น NULL และลบโหนดปัจจุบัน

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

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node* next;
};

void push(struct Node** ref, int new_data) {
    // เพิ่มโหนด
    struct Node* new_n = new Node;
    new_n->data = new_data;
    new_n->next = (*ref);
    (*ref) = new_n;
}

int main() {
    Node* head = NULL;
    push(&head, 12);
    push(&head, 29);
    push(&head, 11);
    push(&head, 23);
    push(&head, 8);
    
    auto curr = head, prev = head;
    
    if (!curr || !curr->next) { // ถ้าลิสต์ว่างหรือมีแค่ 1 โหนด
        cout << "Empty\n";
    } else {
        while (curr) { // วนจน curr == NULL
            if (!curr->next) { // ถ้าเป็นโหนดสุดท้าย
                prev->next = NULL;
                delete(curr); // ปล่อยหน่วยความจำ
                break;
            }
            prev = curr;
            curr = curr->next; // ไปโหนดถัดไป
        }
    }
    
    for (Node* temp = head; temp != NULL; temp = temp->next) // พิมพ์ข้อมูล
        cout << temp->data << " ";
    
    return 0;
}

ผลลัพธ์

8 23 11 29

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

ในวิธีนี้ เราเดินผ่านลิสต์ ติดตาม current และ previous node ตอนที่ current กลายเป็นโหนดสุดท้าย เราเปลี่ยน previous->next เป็น NULL และลบ current node Time Complexity ทั้งหมดคือ O(N) โดย N คือขนาดของลิสต์

สรุป

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