C++程序寻找链表长度

链表是一种常用的数据结构，它不像数组一样需要预先分配一定大小的内存，可以随时添加和删除数据。但是，链表的一个缺点是不方便查找长度。因此，本文将介绍如何编写一个C++程序来计算链表的长度。

链表的定义

链表是一组节点组成的集合，每个节点都包含两个部分，一个是数据部分，另一个是指向下一个节点的指针。链表的头节点是第一个节点，也就是整个链表的起点。

下面是一个简单的链表定义示例，包含了节点的数据类型和链表的数据类型：

struct ListNode {
    int val;        // 节点的数据部分
    ListNode *next; // 节点的指针部分，指向下一个节点
    ListNode(int x) : val(x), next(NULL) {}
};

class LinkedList {
public:
    ListNode *head; // 链表头节点
    LinkedList() { head = NULL; } // 构造函数，初始化链表为空
};

计算链表长度

要计算链表的长度，我们只需要从头节点开始顺序遍历整个链表，直到遇到空节点为止。为了方便起见，我们可以编写一个函数来计算链表长度。

下面是使用循环的方法来实现计算链表长度的函数：

int getLength(LinkedList *list) {
    int len = 0;
    ListNode *p = list->head;
    while (p != NULL) {
        ++len;
        p = p->next;
    }
    return len;
}

函数中使用一个计数器len来记录链表的长度，指针p用来指向当前节点。循环中不断将p指向下一个节点，直到p指向空节点为止，此时链表长度为len。

我们也可以使用递归的方法来计算链表长度，如下所示：

int getLengthRecursion(ListNode *node) {
    if (node == NULL) {
        return 0; // 空节点的长度为0
    } else {
        return 1 + getLengthRecursion(node->next); // 不断递归到下一个节点
    }
}

函数中如果节点为空，则长度为0；否则不断递归到下一个节点，一直到最后一个节点，返回的是递归到该节点的长度+1。

使用示例

我们可以编写一个主函数，来验证计算链表长度的函数是否正确。

下面是一个使用示例，包含了链表的添加和输出功能，以及计算链表长度的功能：

#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class LinkedList {
public:
    ListNode *head;
    LinkedList() { head = NULL; }
    void addNode(int val) {
        if (head == NULL) {
            head = new ListNode(val);
        } else {
            ListNode *p = head;
            while (p->next != NULL) p = p->next;
            p->next = new ListNode(val);
        }
    }
    void printList() {
        ListNode *p = head;
        while (p != NULL) {
            cout << p->val << " ";
            p = p->next;
        }
        cout << endl;
    }
};

int getLength(LinkedList *list) {
    int len = 0;
    ListNode *p = list->head;
    while (p != NULL) {
        ++len;
        p = p->next;
    }
    return len;
}

int main() {
    LinkedList list;
    list.addNode(1);
    list.addNode(2);
    list.addNode(3);
    list.addNode(4);
    list.addNode(5);
    list.printList();
    cout << "Length of the linked list: " << getLength(&list) << endl;
    return 0;
}

输出：