โปรแกรม C++ หาโหนดสุดท้ายที่สองของ Linked List ในการเดินทางครั้งเดียว

ตอนนี้เราจะดูวิธีการหาองค์ประกอบสุดท้ายที่สองใน linked list สมมติว่ามีองค์ประกอบบางอย่างเช่น [10, 52, 41, 32, 69, 58, 41] องค์ประกอบสุดท้ายที่สองคือ 58

เพื่อแก้ปัญหานี้ เราจะใช้ตัวชี้สองตัว ตัวหนึ่งจะชี้ไปยังโหนดปัจจุบัน และอีกตัวจะชี้ไปยังโหนดก่อนหน้าของตำแหน่งปัจจุบัน จากนั้นเราจะเลื่อนจนกว่า next ของ current จะเป็น null แล้วคืนค่าโหนดก่อนหน้า

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

#include <iostream>
using namespace std;

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

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

int secondLastElement(Node *start) {
    Node *curr = start, *prev = NULL;
    while(curr->next != NULL){
        prev = curr;
        curr = curr->next;
    }
    return prev->data;
}

int main() {
    Node* start = NULL;
    prepend(&start, 15);
    prepend(&start, 20);
    prepend(&start, 10);
    prepend(&start, 9);
    prepend(&start, 7);
    prepend(&start, 17);
    cout << "Second last element is: " << secondLastElement(start);
}

ผลลัพธ์

Second last element is: 20