Ở đây chúng ta sẽ xem cách tìm độ dài của danh sách được liên kết bằng cách sử dụng phương pháp lặp lại và đệ quy. Nếu con trỏ đầu được cung cấp, chúng ta phải làm theo các bước sau để lấy độ dài.
-
Đối với phương pháp lặp lại -
-
Lấy phần đầu của danh sách, cho đến khi con trỏ hiện tại không rỗng, hãy chuyển đến nút tiếp theo và tăng số lượng.
-
-
Đối với cách tiếp cận đệ quy -
- Chuyển head làm đối số, điều kiện cơ sở là khi đối số là rỗng thì trả về 0, nếu không thì nhập đệ quy vào danh sách và gửi nút tiếp theo từ nút hiện tại, trả về 1 + độ dài của danh sách con
Ví dụ
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
};
void append(struct Node** start, int data) {
struct Node* new_node = new Node;
new_node->data = data;
new_node->next = (*start);
(*start) = new_node;
}
int count_recursive(Node* start) {
if (start == NULL)
return 0;
return 1 + count_recursive(start->next);
}
int count_iterative(Node* start) {
int count = 0;
Node* current = start;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
int main() {
Node* start = NULL;
append(&start, 1);
append(&start, 3);
append(&start, 1);
append(&start, 2);
append(&start, 1);
cout << "Node count using iterative approach: " << count_iterative(start) << endl;
cout << "Node count using recursion: " << count_recursive(start);
} Đầu ra
Node count using iterative approach: 5 Node count using recursion: 5