c++中如何计算链表长度_c++链表长度计算方法-C++-PHP中文网

c++中如何计算链表长度_c++链表长度计算方法

下次还敢

发布： 2025-09-27 15:58:01

原创

565人浏览过

计算链表长度通常采用遍历法，从头节点开始逐个访问节点并计数，直到指针为空，时间复杂度为O(n)；也可使用递归方法，代码简洁但可能栈溢出；若频繁查询长度，建议在链表类中维护size变量，插入或删除时同步更新，以提高效率。

c++中如何计算链表长度_c++链表长度计算方法

在C++中计算链表长度，通常通过遍历链表节点来实现。只要链表没有维护一个记录长度的成员变量，就需要从头节点开始逐个访问每个节点，直到到达末尾（即指针为nullptr），同时用计数器累加节点数量。

定义链表节点结构

首先需要定义链表的节点结构。常见的单链表节点如下：

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

登录后复制

遍历法计算链表长度

使用一个指针从头到尾遍历链表，每经过一个节点，计数器加1。

int getLength(ListNode* head) {
    int length = 0;
    ListNode* current = head;
    while (current != nullptr) {
        length++;
        current = current->next;
    }
    return length;
}

登录后复制

说明：

head 是链表的头指针。
如果链表为空（head == nullptr），返回 0。
时间复杂度为 O(n)，n 为链表节点数。

递归方法计算长度

也可以使用递归方式，代码更简洁，但可能消耗更多栈空间。

立即学习“C++免费学习笔记（深入）”；

算家云

高效、便捷的人工智能算力服务平台

查看详情

int getLengthRecursive(ListNode* head) {
    if (head == nullptr) {
        return 0;
    }
    return 1 + getLengthRecursive(head->next);
}

登录后复制

说明：

递归终止条件是当前节点为空。
每一层返回 1 加上后续链表的长度。
适合理解逻辑，但在链表很长时可能导致栈溢出。

优化：维护长度变量

如果频繁查询链表长度，可以在链表类中增加一个size变量，在插入或删除节点时同步更新，避免每次遍历。

class LinkedList {
private:
    ListNode* head;
    int size;
public:
    LinkedList() : head(nullptr), size(0) {}
<pre class='brush:php;toolbar:false;'>void addFront(int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    head = newNode;
    size++;
}

int getLength() {
    return size;
}

登录后复制

};

基本上就这些。根据实际需求选择遍历、递归或维护长度的方式。小规模链表用遍历最直接，高频操作建议维护长度。

以上就是c++++中如何计算链表长度_c++链表长度计算方法的详细内容，更多请关注php中文网其它相关文章！