设计一个算法,计算单链表中数据域值为x的结点个数。
时间: 2024-09-26 16:11:32 浏览: 61
设计一个算法来计算单链表中数据域值为 `x` 的节点个数,可以采用遍历链表的方式。这里提供一种基于迭代的解决方案:
1. 定义两个指针,一个普通指针 `p` 和一个快指针 `q`,初始化都为链表头节点。
2. 当快指针 `q` 不为空时,执行循环:
a. 检查 `p` 指针指向的节点的数据域是否等于 `x`。如果相等,则计数器加一。
b. 将 `p` 指针向前移动一步,即 `p = p->next`。
c. 快指针 `q` 向前移动两步,即 `q = q->next`。
3. 循环结束后,`p` 指针将停在最后一个被检查过的节点,因为快指针每次走两步。这时,如果你需要统计的是包含头节点的次数,计数器加一;如果不是,直接返回计数器的值。
```cpp
int countNodesWithValue(ListNode* head, int x) {
ListNode* p = head;
ListNode* q = head;
int count = 0;
while (q != nullptr) {
if (p->val == x) {
count++;
}
p = p->next;
q = q->next ? q->next : nullptr; // 判断q是否为空
}
return count;
}
```
其中,`ListNode` 是链表节点的结构体,通常包含 `val` 存储节点值,`next` 指向下个节点。注意在实际操作中,你需要先定义好这个数据结构。
阅读全文