Cho các giá trị nguyên sẽ được dùng để tạo một danh sách liên kết. Nhiệm vụ là chèn và duyệt danh sách liên kết đơn bằng phương pháp đệ quy.
Chèn nút đệ quy vào cuối
Nếu head là NULL → thêm nút vào head.
Ngược lại thêm vào head->next.
Duyệt nút đệ quy
Nếu head là NULL → thoát.
Ngược lại in head->data và duyệt head->next.
Ví dụ
Đầu vào - 1 - 2 - 7 - 9 - 10
Đầu ra - Danh sách liên kết: 1 → 2 → 7 → 9 → 10 → NULL
Đầu vào - 12 - 21 - 17 - 94 - 18
Đầu ra - Danh sách liên kết: 12 → 21 → 17 → 94 → 18 → NULL
Phương pháp sử dụng trong chương trình dưới đây
Trong phương pháp này, sử dụng các hàm để thêm nút và duyệt danh sách liên kết đơn, gọi chúng đệ quy cho đầu vào tiếp theo.
Định nghĩa cấu trúc SLLNode với int data và con trỏ SLLNode* next.
Hàm addtoEnd(SLLNode* head, int data) nhận con trỏ head của danh sách và dữ liệu nguyên, thêm nút vào cuối danh sách.
Nếu head là NULL thì danh sách rỗng, tạo nút mới, gán làm head, head->next = NULL. Trả về con trỏ nút này.
Nếu head không NULL thì thêm nút vào head->next bằng head->next = addtoEnd(head->next, data).
Hàm traverseList(SLLNode* head) bắt đầu duyệt từ head và in từng giá trị.
Nếu head là NULL thì in NULL và trả về.
Ngược lại in giá trị data và duyệt next bằng traverseList(head->next).
Trong main tạo danh sách bằng addtoEnd() và in danh sách bằng traverseList().
Ví dụ mã
#include <bits/stdc++.h> using namespace std; struct SLLNode { int data; SLLNode* next; }; SLLNode* addtoEnd(SLLNode* head, int data){ if (head == NULL){ SLLNode *nodex = new SLLNode; nodex->data = data; nodex->next = NULL; return nodex; } else{ head->next = addtoEnd(head->next, data); } return head; } void traverseList(SLLNode* head){ if (head == NULL){ cout <<"NULL"; return; } cout << head->data << " -> "; traverseList(head->next); } int main(){ SLLNode* head1 = NULL; head1 = addtoEnd(head1, 1); head1 = addtoEnd(head1, 8); head1 = addtoEnd(head1, 56); head1 = addtoEnd(head1, 12); head1 = addtoEnd(head1, 34); cout<<"Danh sách liên kết là :"<<endl; traverseList(head1); return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Danh sách liên kết là : 1 -> 8 -> 56 -> 12 -> 34 -> NULL