ลบโหนดท้าย (Tail Node) จาก Singly Linked List ที่กำหนดโดยใช้ C++

Linked List เป็นโครงสร้างข้อมูลเชิงเส้นที่มีโหนดและแต่ละโหนดมีสองฟิลด์ หนึ่งคือค่าหรือข้อมูลที่จะแทรกและอีกฟิลด์หนึ่งเก็บที่อยู่ของโหนดถัดไป

งานของเราที่นี่คือลบโหนดจากท้ายของ Linked List โหนดสุดท้ายเรียกว่า tail node หากไม่มีโหนดใน Linked List ให้คืนค่า NULL

ตัวอย่าง

อินพุต 1

1 → 2 → 3 → 4 → 5

เอาต์พุต

1 → 2 → 3 → 4 →

คำอธิบาย

ใน singly linked list ที่กำหนด โหนดจากท้ายคือ '5' หลังจากลบโหนดสุดท้าย เอาต์พุตจะเป็น 1 → 2 → 3 → 4 →

อินพุต 2

5 → 8 → 3

เอาต์พุต

5 → 8 →

คำอธิบาย

ใน singly linked list ที่กำหนด โหนดจากท้ายคือ '3' หลังจากลบโหนดจากท้าย เอาต์พุตจะเป็น 5 → 8 →

วิธีการแก้ปัญหา

วิธีง่ายๆ ในการแก้ปัญหานี้คือสร้าง previous node ที่จะเก็บค่าของ current node เมื่อ current pointer จะชี้ไปที่โหนดสุดท้ายของ linked list

วนลูปผ่านโหนดทั้งหมดของ linked list ถ้า current node ชี้ไปที่โหนดสุดท้าย และสุดท้ายคืนค่าจาก linked list

• เริ่มต้น linked list โดยการแทรกโหนดเข้าไป
• ฟังก์ชัน insertAtFirst(node*& head, int data) จะแทรกโหนดทั้งหมดใน linked list
• ฟังก์ชัน deleteAtTail(node* head) รับ pointer ที่ชี้ไปที่ head ปัจจุบัน
• สร้าง Previous Node pointer และเริ่มต้นเป็น NULL
• สร้าง Temporary Node pointer ที่ชี้ไปที่ head ของ pointer ปัจจุบัน
• วนลูป temporary pointer จนกว่าจะถึงท้ายของ linked list
• เก็บค่าของ temporary pointer ไว้ใน previous node pointer
• ลบ temporary pointer
• คืนค่า linked list

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

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int d) {
        data = d;
        next = NULL;
    }
};

void insertAtFirst(Node* &head, int data) {
    Node* n = new Node(data);
    n->next = head;
    head = n;
}

void printNode(Node* head) {
    while (head != NULL) {
        cout << head->data << "->";
        head = head->next;
    }
    cout << endl;
}

void deleteAtTail(Node* head) {
    Node* prev = NULL;
    Node* temp = head;
    
    while (temp->next != NULL) {
        prev = temp;
        temp = temp->next;
    }
    
    delete temp;
    prev->next = NULL;
    return;
}

int main() {
    Node* head = NULL;
    insertAtFirst(head, 5);
    insertAtFirst(head, 4);
    insertAtFirst(head, 3);
    insertAtFirst(head, 2);
    insertAtFirst(head, 1);
    deleteAtTail(head);
    printNode(head);
    return 0;
}

ผลลัพธ์

การรันโค้ดด้านบนจะสร้างเอาต์พุตเป็น

1 → 2 → 3 → 4 →

ใน singly linked list อินพุตที่กำหนด 1 → 2 → 3 → 4 → 5 โหนดสุดท้ายของ linked list คือ '5' ดังนั้นหลังจากลบโหนดสุดท้าย linked list จะกลายเป็น 1 → 2 → 3 → 4 →