写出判断链表中值为x的结点个数的代码
时间: 2023-03-20 20:00:40 浏览: 76
以下是判断链表中值为x的结点个数的代码,假设链表节点的数据为整数类型:
```python
def count_nodes_with_value(head, x):
count = 0
current_node = head
while current_node != None:
if current_node.data == x:
count += 1
current_node = current_node.next
return count
```
这个函数接受链表的头节点 `head` 和要查找的值 `x`,然后遍历整个链表,每当找到一个节点的值等于 `x`,就将计数器 `count` 增加 1。最后返回计数器 `count` 的值,即为链表中值为 `x` 的节点个数。
相关问题
递归删除不带头结点的链表中值为x的结点
递归删除不带头结点的链表中值为x的结点,可以分为两种情况:
1. 如果当前链表为空,直接返回空链表。
2. 如果当前链表不为空,则需要递归处理当前链表的子链表。如果当前结点的值等于x,则应该将当前结点删除,并返回子链表。否则,应该保留当前结点,并递归处理子链表。
以下是一个示例代码实现:
```
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* deleteNode(ListNode* head, int x) {
if (!head) {
return NULL;
}
if (head->val == x) {
ListNode *temp = head;
head = head->next;
delete temp;
return deleteNode(head, x);
} else {
head->next = deleteNode(head->next, x);
return head;
}
}
```
在上面的代码中,我们首先判断当前链表是否为空。如果为空,直接返回空链表。否则,判断当前结点的值是否等于x。如果等于x,则将当前结点删除,并返回子链表;否则,保留当前结点,并递归处理子链表。最终返回处理后的链表头指针。
删除链表中值为x的全部结点
可以使用双指针来解决这个问题。我们用一个指针 `pre` 指向当前节点的前一个节点,用另一个指针 `cur` 指向当前节点。如果当前节点的值等于 `x`,我们将 `pre` 的 `next` 指针指向 `cur` 的 `next`,然后将 `cur` 指针移动到 `cur.next`。如果当前节点的值不等于 `x`,我们就将 `pre` 和 `cur` 指针都向前移动一个节点。
具体实现如下:
```python
def removeElements(head, val):
# 处理头结点为要删除的节点的情况
while head and head.val == val:
head = head.next
if not head:
return None
pre = head
cur = head.next
while cur:
if cur.val == val:
pre.next = cur.next
cur = cur.next
else:
pre = cur
cur = cur.next
return head
```
时间复杂度是 $O(n)$,其中 $n$ 是链表的长度,空间复杂度是 $O(1)$。