用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) （只需要常数个额外的指针变量）

相关问题

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

假设L是一个带头结点的单链表，用python语言设计递归算法使单链表L逆置

以下是Python的递归算法实现单链表L的逆置：

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

def reverseList(head: Node) -> Node:
    if not head or not head.next:
        return head
    newHead = reverseList(head.next)
    head.next.next = head
    head.next = None
    return newHead

在这个递归算法中，我们首先判断传入的单链表是否为空或者只有一个节点，如果是，直接返回原来的链表头。否则，我们递归调用函数，将链表的后续部分逆置，得到新的链表头newHead。然后，我们将原链表头head的next节点的next指针指向head，将head的next指针指向None，即将head节点插入到逆置后的链表的末尾。最后，返回新的链表头newHead即可。