Tìm độ dài danh sách liên kết bằng cách lặp và đệ quy. Cho con trỏ head, làm theo các bước:
- Cách lặp: lấy head, cho đến current không null, đi next và tăng đếm.
- Cách đệ quy: truyền head, cơ sở null trả 0, ngược lại đệ quy next, trả 1 + độ dài danh sách con.
Ví dụ mã nguồn
#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); } Kết quả
Node count using iterative approach: 5 Node count using recursion: 5