Cho một danh sách liên kết đơn và số nguyên dương N làm đầu vào. Mục tiêu là tìm nút thứ N từ cuối trong danh sách đã cho bằng đệ quy. Nếu danh sách đầu vào có các nút a → b → c → d → e → f và N = 4 thì nút thứ 4 từ cuối sẽ là c.
Chúng ta sẽ duyệt đến nút cuối cùng trong danh sách và khi quay lại từ đệ quy (backtracking) tăng biến đếm. Khi biến đếm bằng N thì trả về con trỏ đến nút hiện tại làm kết quả.
Các trường hợp đầu vào/đầu ra
Đầu vào - Danh sách: 1 → 5 → 7 → 12 → 2 → 96 → 33, N=3
Đầu ra - Nút thứ N từ cuối là: 2
Giải thích - Nút thứ 3 từ cuối là 2.
Đầu vào - Danh sách: 12 → 53 → 8 → 19 → 20 → 96 → 33, N=8
Đầu ra - Nút không tồn tại.
Giải thích - Danh sách chỉ có 7 nút nên không thể có nút thứ 8 từ cuối.
Phương pháp sử dụng trong chương trình dưới đây
Trong phương pháp này, chúng ta đệ quy đến cuối danh sách và khi quay lại (backtracking) tăng biến đếm tĩnh. Ngay khi biến đếm bằng N đầu vào, trả về con trỏ nút hiện tại.
Định nghĩa cấu trúc Node với phần dữ liệu int và con trỏ Node* next.
Hàm addtohead(Node** head, int data) thêm nút vào đầu để tạo danh sách liên kết đơn.
Tạo danh sách liên kết đơn bằng hàm trên với head trỏ đến nút đầu.
Hàm display(Node* head) in danh sách liên kết từ nút head.
Nhập N là số nguyên dương.
Hàm findNode(Node* head, int n1) nhận con trỏ head và n1, in kết quả khi tìm thấy nút thứ n1 từ cuối.
Khai báo con trỏ nlast trỏ đến nút thứ n1 từ cuối.
Gọi searchNthLast(head, n1, &nlast) để tìm nút đó.
Hàm searchNthLast(Node* head, int n1, Node** nlast) trả về con trỏ đến nút thứ n1 từ cuối trong danh sách có head là nút đầu.
Khai báo biến đếm tĩnh count.
Nếu head là NULL thì trả về.
Lấy tmp = head->next.
Gọi đệ quy searchNthLast(tmp, n1, nlast) để duyệt đến nút cuối.
Sau đó tăng count lên 1.
Nếu count bằng n1 thì gán *nlast = head.
Cuối cùng in giá trị nút do nlast trỏ đến.
Ví dụ mã
#include <bits/stdc++.h> using namespace std; struct Node { int data; Node* next; }; void addtohead(Node** head, int data){ Node* nodex = new Node; nodex->data = data; nodex->next = (*head); (*head) = nodex; } void searchNthLast(Node* head, int n1, Node** nlast){ static int count=0; if (head==NULL){ return; } Node* tmp=head->next; searchNthLast(tmp, n1, nlast); count = count + 1; if (count == n1){ *nlast = head; } } void findNode(Node* head, int n1){ Node* nlast = NULL; searchNthLast(head, n1, &nlast); if (nlast == NULL){ cout << "Nút không tồn tại"; } else{ cout << "Nút thứ N từ cuối là: "<< nlast->data; } } void display(Node* head){ Node* curr = head; if (curr != NULL){ cout<<curr->data<<" "; display(curr->next); } } int main(){ Node* head = NULL; addtohead(&head, 20); addtohead(&head, 12); addtohead(&head, 15); addtohead(&head, 8); addtohead(&head, 10); addtohead(&head, 4); addtohead(&head, 5); int N = 2; cout<<"Danh sách liên kết là :"<<endl; display(head); cout<<endl; findNode(head, N); return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Danh sách liên kết là : 5 4 10 8 15 12 20 Nút thứ N từ cuối là: 12