Tìm nút áp chót của danh sách liên kết trong một lần duyệt C++

Bây giờ ta sẽ thấy cách lấy phần tử áp chót trong danh sách liên kết. Giả sử có các phần tử như [10, 52, 41, 32, 69, 58, 41], phần tử áp chót là 58.

Để giải quyết, ta dùng hai con trỏ: một trỏ đến nút hiện tại, một trỏ đến nút trước đó của vị trí hiện tại, sau đó di chuyển cho đến khi next của current là null, rồi trả về nút trước đó.

Ví dụ mã nguồn

#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); }

Kết quả

Second last element is: 20