Cho một danh sách liên kết Singly và số nguyên dương N làm đầu vào. Mục đích là tìm nút thứ N từ cuối trong danh sách đã cho bằng cách sử dụng đệ quy. Nếu danh sách đầu vào có các nút a → b → c → d → e → f và N là 4 thì nút thứ 4 từ cuối sẽ là c.
Trước tiên, chúng ta sẽ đi qua cho đến nút cuối cùng trong danh sách và trong khi quay trở lại từ số gia tăng đệ quy (quay lui). Khi số đếm bằng N thì kết quả là trả về con trỏ đến nút hiện tại.
Hãy để chúng tôi xem các kịch bản đầu ra đầu vào khác nhau cho việc này -
Đầu vào - Danh sách:- 1 → 5 → 7 → 12 → 2 → 96 → 33 N =3
Đầu ra - Node thứ từ cuối cùng là:2
Giải thích - Nút cuối cùng thứ 3 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 sẽ không thể có nút cuối cùng thứ 8.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, trước tiên chúng ta sẽ đến cuối danh sách bằng cách sử dụng đệ quy và trong khi theo dõi ngược, chúng ta sẽ tăng một biến đếm tĩnh. Ngay sau khi số đếm bằng với đầu vào N, hãy trả về con trỏ nút hiện tại.
-
Lấy cấu trúc Node với phần dữ liệu int và Node làm con trỏ tiếp theo.
-
Hàm addtohead (Node ** head, int data) được sử dụng để thêm các nút vào head để tạo một danh sách được liên kết duy nhất.
-
Tạo một danh sách được liên kết đơn lẻ bằng cách sử dụng chức năng trên với head là con trỏ đến nút đầu tiên.
-
Hiển thị hàm (Node * head) được sử dụng để in danh sách liên kết bắt đầu từ nút head.
-
Lấy N là số nguyên dương.
-
Hàm findNode (Node * head, int n1) nhận con trỏ đến đầu và n1 và in kết quả khi tìm thấy nút thứ n1 từ cuối.
-
Lấy blast làm con trỏ đến nút thứ n 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 cuối cùng thứ n từ cuối trong danh sách được liên kết với đầu là nút đầu tiên.
-
Lấy một biến đếm tĩnh.
-
Nếu đầu là NULL, không trả về gì.
-
Hãy tmp =head-> tiếp theo.
-
Gọi searchNthLast (tmp, n1, nlast) để duyệt đệ quy cho đến nút cuối cùng.
-
Sau đó, số lượng tăng thêm là 1.
-
Nếu số đếm bằng n1 thì hãy đặt * nlast =head.
-
Ở cuối in giá trị của nút được trỏ bởi nlast là kết quả.
Ví dụ
#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 << "Node does not exists";
}
else{
cout << "Nth Node from the last is: "<< 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<<"Linked list is :"<<endl;
display(head);
cout<<endl;
findNode(head, N);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
Linked list is : 5 4 10 8 15 12 20 Nth Node from the last is: 12