给出计算一个单项链表所有节点数量的递归算法

以下是计算单项链表所有节点数量的递归算法，假设链表中每个节点都有一个指向下一个节点的指针：

int countNodes(Node* head) {
    if (head == NULL) {  // 如果链表为空，则节点数量为0
        return 0;
    }
    else {
        return 1 + countNodes(head->next);  // 递归调用，每次加1
    }
}

该算法的基本思路是，如果链表为空，则节点数量为0，否则将节点数量加1并递归调用函数来计算下一个节点的数量。最终，当遍历完整个链表时，返回节点数量的总和。

相关问题

用python给出计算一个单项链表所有节点数量的递归算法

以下为Python代码实现：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def countNodes(head: ListNode) -> int:
    if head is None:  # 链表为空，节点数量为0
        return 0
    else:
        return 1 + countNodes(head.next)

# 测试
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n1.next = n2
n2.next = n3

print(countNodes(n1))  # 输出3

首先定义了一个`ListNode`类来表示单项链表的节点，其中`val`表示节点的值，`next`表示指向下一个节点的指针。

然后定义了递归函数`countNodes`，它的参数是链表的头节点`head`，返回值是链表中节点的数量。如果链表为空，节点数量为0；否则，节点数量等于头节点之后节点的数量加1。

最后，我们创建了一个简单的单项链表并进行了测试。链表中有3个节点，因此输出为3。

设计一个递归算法删除链表中第一个值为x的结点

设计一个递归算法来删除链表中第一个值为 `x` 的节点，首先我们需要明确递归的基本思路。假设我们有一个单向链表 `head` 和目标值 `x`，递归函数可以分为两个步骤：

1. **基本情况** (Base Case): 如果链表的头节点值就是 `x`，则直接返回下一个节点作为新链表的头。
2. **递归情况** (Recursive Case): 否则，如果头节点不是 `x`，我们就将头节点指向的下一个节点传递给递归函数，并在返回时忽略当前节点。

下面是一个 Python 示例实现这个递归算法：

def remove_first_node_with_x(head, x):
    # Base case: 当链表为空，或者头节点值为x时，返回None
    if head is None or head.val == x:
        return None

    # Recursive case: 调用自身，传入下一个节点
    head.next = remove_first_node_with_x(head.next, x)
    
    # 返回结果
    return head

在这个函数中，每次递归调用都会检查当前节点是否需要删除，如果不是，则继续递归处理下一个节点。当找到值为 `x` 或者遍历到链表尾部时，递归会结束，最终返回修改后的链表头部。