用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。

相关问题

用python仅适用固定数量的额外空间，并且不适用任何递归，详细阐述一个逆置单项链表L的算法

算法思路：

- 创建一个新的链表，作为逆置后的链表。
- 遍历原链表，将每个节点插入到新链表的头部。
- 返回新链表作为逆置后的链表。

算法步骤：

1. 创建一个新链表，并将其头节点设置为 None。
2. 遍历原链表，每次取出一个节点，将其插入到新链表的头部。
3. 返回新链表。

Python 代码实现：

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

def reverseList(head: Node) -> Node:
    # 创建一个新链表，头节点为 None
    new_head = Node()

    # 遍历原链表
    while head:
        # 取出原链表中的头节点
        cur = head
        head = head.next

        # 将取出的节点插入到新链表的头部
        cur.next = new_head.next
        new_head.next = cur

    # 返回新链表
    return new_head.next

时间复杂度：O(n)

空间复杂度：O(1) （只需要常数个额外的指针变量）

设计一个递归算法删除链表中第一个值为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` 或者遍历到链表尾部时，递归会结束，最终返回修改后的链表头部。